Saving tons of PRP-C and (hypotetical) LL-C tests, a new method

[preda]

Originally Posted by R. Gerbicz

f(p,e+1)=(3*f(p,e)+c)%(2^512) for some c=0,1,2

OK. So I have res512(e) == f(p,e)%(2^512).
Now, if I choose res64 to be the *top* 64 bits of the res512 instead of the bottom 64 bits, when I do the mul-by-3 to derive f(p, e+1), the addition of "c" (being 0, 1, or 2) to 3*f(p,e) is very unlikely to change the top 64 bits of the 512 bits. 1/(2^(512-64))-likely. So practically, the "c" does not influence the top 64 bits of res512 in a mul-by-3 step.

In a div-by-3, probably the carry moves the other way around, and thus the bottom "64" bits are unlikely to be affected. Putting the 64 bits in the middle of the 512 bits, we can do both mul and div-by-3 disregarding "c".

[R. Gerbicz]

Originally Posted by preda

OK. So I have res512(e) == f(p,e)%(2^512).
Now, if I choose res64 to be the *top* 64 bits of the res512 instead of the bottom 64 bits, when I do the mul-by-3 to derive f(p, e+1), the addition of "c" (being 0, 1, or 2) to 3*f(p,e) is very unlikely to change the top 64 bits of the 512 bits. 1/(2^(512-64))-likely. So practically, the "c" does not influence the top 64 bits of res512 in a mul-by-3 step.

Yes.

Originally Posted by preda

In a div-by-3, probably the carry moves the other way around, and thus the bottom "64" bits are unlikely to be affected. Putting the 64 bits in the middle of the 512 bits, we can do both mul and div-by-3 disregarding "c".

No, the difference of those residues is a small multiple of Mod(1,2^512)/3, and

(18:55) gp > binary(lift(Mod(1,2^512)/3))
%39 = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1]
(18:55) gp >

and for me it is much more natural to store the low bits than the top bits or some bits from the middle.
And there could be some misunderstanding here, because the mult by 3 comes from the f(p,e) to f(p,e+1) step, and the division coming from the reverse direction, when we know f(p,e+1) and we want to get f(p,e). So from what residue you'd get at once the mult by 3 and div by 3 ?

[preda]

Concretely, I was thinking that when moving to a much larger residue, such as res512, we should take from the full Mp bits:


res512 := bits[Mp-256:Mp-1] + bits[0:255]
instead of bits[0:511].


Would such a setup of res512 be a problem for your algorithm?

[axn]

Originally Posted by preda

Would such a setup of res512 be a problem for your algorithm?

I believe such a mix-and-match residue is useless for the proposed algorithm. You strictly need low order n bits for the algorithm to correctly work.

[axn]

Originally Posted by R. Gerbicz

Maybe there could be a dozen or so such p, where mp is not completely factored, but d>2^512.
We could switch to res1024 only for say p>2^32.
And ofcourse you'd to store it only if you have a completed LL/PRP test to save space in database.

IIUC, the more excess bits you have, the less likely a false positive will happen. Sure, 512 is good enough for today's purpose, but the additional cost of moving directly to 1024 is negligible, and will avoid future changes and other complications. Anyway, just something to think about for TPTB.

[preda]

Originally Posted by axn

I believe such a mix-and-match residue is useless for the proposed algorithm. You strictly need low order n bits for the algorithm to correctly work.

It's not "mix-and-match". It's just a contiguous block of 512 bits, but starting at a different position than 0. I don't know if the particular "0" is essential or not.


For LL, the "-2" applied at the 0 position makes that position special. But nothing makes bit-0 particular for PRP; it's a "perfect circle" with all bit positions equivalent.

[R. Gerbicz]

Originally Posted by axn

I believe such a mix-and-match residue is useless for the proposed algorithm. You strictly need low order n bits for the algorithm to correctly work.

Right, even if that could work (we're speaking about elementary Maths), what would give to the algorithm? Note that in (3^mp mod mp) mod (2^512) calculation you're also using squaring, like in LLT, and that is mixing up the residue just in one iteration, even if you change a single low bit:

(14:21) gp > p=20011;mp=2^p-1;x=random(mp);
(14:21) gp > x2=Mod(x^2,mp);
(14:21) gp > y=x+(1-2*bittest(x,64))*2^64;
(14:21) gp > y2=Mod(y^2,mp);
(14:21) gp > vecsum(binary(bitxor(lift(x2),lift(y2))))
%32 = 10075
(14:21) gp > y-x
%33 = 18446744073709551616
(14:21) gp >

Changed only 1 bit of x, the 64-th bit. Done a squaring and the residue of x^2 changed in 10075 bit positions, close to p/2~10005. Storing higher bits gives nothing.

Originally Posted by axn

IIUC, the more excess bits you have, the less likely a false positive will happen. Sure, 512 is good enough for today's purpose, but the additional cost of moving directly to 1024 is negligible, and will avoid future changes and other complications. Anyway, just something to think about for TPTB.

In any case you'd need to increase the number of bits, because even the smallest divisors are increasing q>=2*p+1, so the d values will be alse bigger.

[preda]

Originally Posted by R. Gerbicz

Right, even if that could work (we're speaking about elementary Maths), what would give to the algorithm?

So what you're saying is that even if it would work, there would be no benefit. You're not saying that it does not work, right?

[R. Gerbicz]

Originally Posted by preda

So what you're saying is that even if it would work, there would be no benefit. You're not saying that it does not work, right?

Correct, and I feel that your method wouldn't work.

[preda]

Originally Posted by R. Gerbicz

Correct, and I feel that your method wouldn't work.

OK. Maybe the residue must be taken at 0.

Anyway, cool idea!

How much work do you estimate would be saved? If I understand correctly, the benefit kicks in when a single factor "d" of Mp is known, and Mp has at least one other factor. (i.e. Mp/d is composite).

If Mp/d is prime, is an additional PRP test still needed to "prove" it?

What if two factors d1 and d2 of Mp are known. Is a PRP test needed to decide Mp/d1/d2?

[axn]

Originally Posted by preda

What if two factors d1 and d2 of Mp are known. Is a PRP test needed to decide Mp/d1/d2?

As long as the product of the factors stays < 512 (or whatever) bits, the method will work. Just use Mp/d where d=d1*d2*...