Quote:
Originally Posted by Citrix
Why? b can be composite.
eg. 7*6^100+11
|
Sure, b can be composite. But a composite b
must also pass a prime b check as a
necessary condition.
For example, consider N=7*6^100+11. It
will pass the b=2 check.
Code:
? N=7*6^100+11;
? N%(2^64)
%2 = 11
? N%(2^65)
%3 = 11
I will also pass b=3 check.
Code:
? N%(3^64)
%4 = 11
? N%(3^65)
%5 = 11
If it didn't pass b=2 check, then no need to check any other even b. If it didn't pass b=3 check, then no need to check any composite base which is multiple of 3, and so on.
So we can limit ourselves to prime bases, as a first pass. In second pass, we subtract the potential c from N (i.e. N - N%(b^k) ) and then trial divide it to see if it factorises into small factors. If so, we get the actual representation as well.