CODEWITHSUNDEEP
algorithmmath
user3029680
user3029680

Reputation: 35

recurrence using (mod 2^32+1)

Where m = 2^32+1 = 641*6700417 the mod function is little more than a single subtract on 32-bit processors. I don’t care that the recurrence
Seed = Seed*a%m
is not a good random number generator. I wish to use it in an encryption algorithm as a 32-bit wide sbox. Is there an algorithm that would return true if a trial value of “a” would cause the recurrence to visit all 2^32 values?

Assuming that such an algorithm exits I suspect that if a*b%m = 1 then the recurrence using “b” would run backwards. Is what I suspect true. I would use “b” to implement the inverse sbox.

I can do everything I ask using mod (2^16+1) but that number is prime.

Upvotes: 0

Views: 143

Answers (2)

DrV
DrV

Reputation: 23530

This is not a very simple question. It is easy to answer that in your case the numbers you use are poor. However, the easy answer: use primes is not the correct answer, either.

If we use the recurrence:

r := (r a) mod m

it is easy to see, that this gives the maximal cycle (m-1) if and only if all a^i mod m give different numbers for i = 0 .. m-2. However, this does not automatically happen even if both a and m are primes.

An example of two primes which cannot be used: a = 13, m = 17, because 13^4 mod 17 == 1, and the cycle will be very short (4 steps).

So, we need some other requirements, as well. To make a very long story short, a generator of this type (multiplicative congruential generator) produces the maximal cycle (m-1) if:

  • m is prime
  • a is a primitive root of m

Unfortunately, the latter requirement is a bit difficult, as there is no general formula to find primitive roots. (And please note that a does not have to be a prime, for example the combination m=17 and a=10 gives the full cycle.)

So, despite this being a seemingly simple problem, it touches some rather fundamental aspects of number theory.

Upvotes: 0

MvG
MvG

Reputation: 60958

Is there an algorithm that would return true if a trial value of “a” would cause the recurrence to visit all 232 values?

Yes there is:

return false;

The most obvious reason is that the set of all 232 possible values includes the value zero, and there the recurrence gets stuck, so it isn't cyclic. But even if you exclude zero, if you start with a multiple of 641, then you will only ever visit multiples of 641, and the same holds for the other factor.

This kind of “visit all values” property only works if you reduce modulo some prime, and if you exclude zero.

Upvotes: 2

Related Questions