Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother?
Ideally I'm looking for something that has random access abilities so i could ask for the 100th item in the set without having to first calculate items 0 to 99.
Also, I would like to be able to specify a minimum value for these numbers, to specify that none of them should less than 50 for example.
Does anyone know of an algorithm to do this, or at least satisfy part of my asks?
Thanks!
Asked By : Alan Wolfe
Answered By : D.W.
Yes. It's possible to satisfy all of your requirements, by combining some standard tools:
Let $F$ be a function that, given a sequence of random bits as input, outputs a random 1000-bit prime. $F$ can be implemented by repeatedly picking a random 1000-bit number, then using a primality test to check if it is prime, and outputting the first prime number you see.
Let $G$ be a pseudorandom generator that expands a short random seed to a long sequence of pseudorandom numbers, e.g., AES-CTR mode.
Let $H$ be a cryptographic hash function, e.g., SHA256.
Let $s$ be a random seed.
Now define
$$f(i) = F(G(H(s,i))).$$
Then the sequence
$$f(1),f(2),f(3),f(4),f(5),\dots$$
satisfies all of your requirements:
Every number in the sequence is prime, and it is super-unlikely that any prime will repeat (this can be quantified using the birthday paradox), so all of the numbers in the sequence are co-prime.
It is super-unlikely that any number will be less than 50. If you prefer an absolute guarantee, you can tweak the definition of $F$ to require that the number is both prime and at least your lower bound.
The sequence can be efficiently computed: each of the building blocks $F,G,H$ has efficient instantiations, so $f$ can be computed efficiently. Moreover, this construction permits efficient random access into the sequence.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47694
0 comments:
Post a Comment
Let us know your responses and feedback