Prev: Why does JH Conway say -1 is prime?
Next: Sum of permutations
From: Charlie-Boo on 30 Jan 2010 16:33
On Jan 24, 12:24 pm, hagman <goo...(a)von-eitzen.de> wrote:
> On 24 Jan., 17:35, TCL <tl...(a)cox.net> wrote:
>
> > On Jan 24, 10:03 am, Charlie-Boo <shymath...(a)gmail.com> wrote:
>
> > > How can I map an integer N between 1 and 1,000,000 to a string f(N) of
> > > 12 letters where I can map back from f(N) to N, and f(N+1) bears no
> > > resemblance to f(N)?  (Better yet f(N+m) bears no resemblance to f(N)
> > > for m=1 to 1000 or f(m) for any m not equal to N.)
>
> > > C-B
>
> > What is the limitation on the length of the strings? If there is none,
> > then there is a trivial answer to your question.
> > -TCL
>
> Prepare a table of 1000000 "random" strings

What is the algorithm to calculate f(N) and the inverse of f, starting
from scratch?

C-B
From: Charlie-Boo on 30 Jan 2010 16:34
On Jan 24, 3:10 pm, TCL <tl...(a)cox.net> wrote:
> On Jan 24, 12:30 pm, HallsofIvy <GeorgeI...(a)netzero.com> wrote:
>
>
>
>
>
> > > On Jan 24, 10:03 am, Charlie-Boo
> > > <shymath...(a)gmail.com> wrote:
> > > > How can I map an integer N between 1 and 1,000,000
> > > to a string f(N) of
> > > > 12 letters where I can map back from f(N) to N, and
> > > f(N+1) bears no
> > > > resemblance to f(N)?  (Better yet f(N+m) bears no
> > > resemblance to f(N)
> > > > for m=1 to 1000 or f(m) for any m not equal to N.)
>
> > > > C-B
>
> > > What is the limitation on the length of the strings?
> > > If there is none,
> > > then there is a trivial answer to your question.
> > > -TCL
>
> >   He DID say "strings of 12 letters".  I interpreted that to me the length of the string is 12.  I guess you could take it to me any string from an alphabet of 12 letters.- Hide quoted text -
>
> > - Show quoted text -
>
> If that is what OP meant, then order the strings in dictionary
> (lexicographic) order. Say the letters are a,b,c,...,l. Then define
> f(1)= the first in the order = aaaaaaaaaaaa
> f(2)= the second in the order = aaaaaaaaaaab
> .....
> That is a one-to-one map.

Note "f(N+1) bears no resemblance to f(N)"

> -TCL- Hide quoted text -
>
> - Show quoted text -

From: Charlie-Boo on 30 Jan 2010 16:51
On Jan 25, 10:43 am, Dan Cass <dc...(a)sjfc.edu> wrote:
> > How can I map an integer N between 1 and 1,000,000 to
> > a string f(N) of
> > 12 letters where I can map back from f(N) to N, and
> > f(N+1) bears no
> > resemblance to f(N)?  (Better yet f(N+m) bears no
> > resemblance to f(N)
> > for m=1 to 1000 or f(m) for any m not equal to N.)
>
> > C-B
>
> Since 26^12 = 95428956661682176,
> you can do much better than 1,000,000.

The problem is this: The user gets the next sequential key, which is f
(1) then f(2) etc, to use to create an account. He should not be able
to guess what key anyone else got, so only a tiny fraction of the 12
letter strings are actual keys, and they can't determine what the
sequence f(1), f(2), f(3)... is by repeatedly requesting a key and
seeing what the pattern is in the values generated since f(N+1) does
not resemble f(N).

That is, when you ask for your own key, it gives you f(N) for the next
N value 1, 2, 3... The problem is to keep them from guessing someone
else's key and using it. This means the keys used will be very sparse
(1,000,000 out of 26^12). I need to create the key f(N) and get the N
back from the key that is entered when they use it. also telling if
the value input by the user is not a legitimate key.

The internal account number is N = 1, 2, 3..., 1000000 while they
access it by entering in f(N) = 12 letters. The problem is to make it
hard for them to guess someone else's key to get into their account,
by making the actual keys a tiny fraction of the possible strings
entered as the key (12 letters), and the sequence of keys f(1), f(2), f
(3)... hard to determine from examining a sequence of them generated
by requesting your own key repeatedly.

C-B
From: Mok-Kong Shen on 31 Jan 2010 18:40
Charlie-Boo wrote:
[snip]

You questioned elsewhere about the problem of inverse. I want
to say that, for the function g(x) I indicated in my follow-up, the
value of g^(-1)(x) can be numerically computed with normally
acceptable cost (31 evaluations of g for 32 bit unsigned int).

M. K. Shen
From: Charlie-Boo on 21 Feb 2010 02:57
On Jan 31, 6:40 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> Charlie-Boo wrote:
>
> [snip]
>
> You questioned elsewhere about the problem of inverse. I want
> to say that, for the function g(x) I indicated in my follow-up, the
> value of g^(-1)(x) can be numerically computed with normally
> acceptable cost (31 evaluations of g for 32 bit unsigned int).
>
> M. K. Shen

I have implemented a scheme. 1st N -> N times A plus B modulo C for
constants A,B,C to make a random looking number. This is the first
half of the key of 12 characters. Then add constant D plus N and
modulo it the size of the second half. This is the 2nd half of the
key of 12 characters.

To get back N I simply compare the 2 halves, minus the D, and the
difference is N. But every "key" gives an N, not just the ones I
generate. They could type in a random key and it would get account N
for some N! How to tell it is one I generate??

Simple. It must be more than some key. It must be the key for N! So
generate the key for N and if that is what they entered then it is one
the user knew from being given it.

I actually code it to a letter plus 2 digits but no similar characters
0 1 5 or I O S U V base 21 + 7 + 7 > 1,000 for each 3 characters e.g.
A32B34Q62Z43 is a key giving an N from 1 to 1,000,000 (accounts) and
only 1 out of 1,000,000 "keys" are actually keys.

THANKS FOR ALL OF THE THEORETICAL STUFF. I WOULD HAVE LOVED TO GO
THROUGH IT NOW I MAY NEVER - MAYBE VERSION 2?

It will be used in a program that will extract formal data as 2-
dimensional tables from web sites automatically - something done only
by programming or limited scope using references to HTML commands.
This is for any site and requires no reference to HTML nor programming
- only choosing a small number of field values from the screen and it
deduces the entire series of lines in the table. 8 years in the
making. Extremely difficult problem. Look up "screen scrapers" and
they are all programming or limited.

C-B
First  |  Prev  | 
Pages: 1 2 3
Prev: Why does JH Conway say -1 is prime?
Next: Sum of permutations