Re: [GENERAL] Feistel cipher, shorter string and hex to int
Ivan Sergio Borgonovo wrote: I don't get the 1366.0 and the 714025.0. Writing 1366.0 isn't going to use float arithmetic? Yes, that's on purpose. Now that you mention it, I think that 1366.0 could be an integer instead, but the division by 714025 and multiplication by 32767 have to be floating point operations. I'm going to see if using bigint is going to make any difference in speed. If you're after more speed, using the C language may be the solution. Finally... if I were (and I'm not) interested in using 30 bit, should I turn that *32767 into a *16383? For shift and bit mask it looks more obvious. To generate a 31 bits (positive) result from a 30 bits input, I would modify the initialisation of the 16 bits blocks so that each of them has the most significant bit set to 0, but without loosing any of the 30 bits. The MSB bits have to be kept at 0 throughout the algorithm. So I'd to that: l1:= ((value >> 16) & 16383) | (value&32768); r1:= value&32767; and indeed reduce the output range of the function: r2:=l1 # 1366.0*r1+150889)%714025)/714025.0)*16383)::int; the rest being identical excepts that it could now return int (and it would be unsigned) instead of bigint. I haven't tested that variant, though. Do you remember the name of this particular F? Not sure it has a specific name, but you'll find related stuff by searching for "linear congruential generator". Everything else seems to need more processing at no real added value. Turning the int into base 32 [0-9A-N] with plpgsql looks expensive just to shorten the string to 4 char. Note that 4 chars would cover a range of 32^4, which is only about one million different values. I think you'd need 7 chars to express up to 2^31 in base 32, because 32^7 < 2^31 < 32^6 Best regards, -- Daniel PostgreSQL-powered mail user agent and storage: http://www.manitou-mail.org -- Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
Re: [GENERAL] Feistel cipher, shorter string and hex to int
On Tue, 07 Jul 2009 12:07:48 +0200 "Daniel Verite" wrote: > Ivan Sergio Borgonovo wrote: > > > r2:=l1 # 1366.0*r1+150889)%714025)/714025.0)*32767)::int; > > -- but what about this? where does it come from? > > This function: > (1366.0*r1+150889)%714025 > implements a known method to get random numbers. I think it comes > from "Numerical recipes" by William Press. > Note that the algorithm is not tied to that function, it could be > replaced by something else (especially one that involves a private > key), but it has to be carefully chosen or the end result won't > look so random. I don't get the 1366.0 and the 714025.0. Writing 1366.0 isn't going to use float arithmetic? Is it there just to avoid an overflow? I'm going to see if using bigint is going to make any difference in speed. Finally... if I were (and I'm not) interested in using 30 bit, should I turn that *32767 into a *16383? For shift and bit mask it looks more obvious. Do you remember the name of this particular F? Since I don't see anything other than to_hex that could "shorten" an int to a string easily and quickly... it seems that returning a signed integer is OK. Everything else seems to need more processing at no real added value. Turning the int into base 32 [0-9A-N] with plpgsql looks expensive just to shorten the string to 4 char. Thanks. -- Ivan Sergio Borgonovo http://www.webthatworks.it -- Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
Re: [GENERAL] Feistel cipher, shorter string and hex to int
Ivan Sergio Borgonovo wrote: r2:=l1 # 1366.0*r1+150889)%714025)/714025.0)*32767)::int; -- but what about this? where does it come from? This function: (1366.0*r1+150889)%714025 implements a known method to get random numbers. I think it comes from "Numerical recipes" by William Press. Note that the algorithm is not tied to that function, it could be replaced by something else (especially one that involves a private key), but it has to be carefully chosen or the end result won't look so random. Best regards, -- Daniel PostgreSQL-powered mail user agent and storage: http://www.manitou-mail.org -- Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
Re: [GENERAL] Feistel cipher, shorter string and hex to int
Ivan Sergio Borgonovo wrote: I need shorter values (because they should be easier to type. To be sure to modify the function in a sensible way I really would appreciate some pointer. Still if it return What exactly is your desired range of output values? Best regards, -- Daniel PostgreSQL-powered mail user agent and storage: http://www.manitou-mail.org -- Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
[GENERAL] Feistel cipher, shorter string and hex to int
On Sat, 02 May 2009 11:26:28 +0200 "Daniel Verite" wrote: > Note that it returns a bigint because we don't have unsigned > integers in PG. If you're OK with getting negative values, the > return type can be changed to int. > Otherwise if you need a positive result that fits in 32 bits, it's > possible to tweak the code to use 15 bits blocks instead of 16, > but then the input will have to be less than 2^30. I need shorter values (because they should be easier to type. To be sure to modify the function in a sensible way I really would appreciate some pointer. Still if it return To further shrink the length of the result I was planning to to_hex (actually it would be nice to have a fast to_35base [0-9a-z])... but I wasn't able to find a way to convert back an hex string to an int. x'fff' seems to work just for literals. CREATE OR REPLACE FUNCTION pseudo_encrypt(value int) returns bigint AS $$ DECLARE l1 int; l2 int; r1 int; r2 int; i int:=0; BEGIN l1:= (value >> 16) & 65535; -- modifying here seems trivial r1:= value&65535; -- l1:= (value >> 15) & B'111'::int; -- r1:= value & B'111'::int; WHILE i<3 LOOP l2:=r1; r2:=l1 # 1366.0*r1+150889)%714025)/714025.0)*32767)::int; -- but what about this? where does it come from? /* r2:=l1 # 1366.0*r1+150889)%714025)/714025.0)*B'11'::int)::int; */ -- ?? l1:=l2; r1:=r2; i:=i+1; END LOOP; return ((l1::bigint<<16) + r1); -- modifying here seems trivial END; $$ LANGUAGE plpgsql strict immutable; Anything else to suggest or copy from? -- Ivan Sergio Borgonovo http://www.webthatworks.it -- Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
