- Pavlos Saridis wrote:

> Gcd (a^N-1,b^N-1) for some choices of a and b

For large N, you would presumably compute a^N-1 modulo N.

Then you should test gcd(a^N-1 mod N,N) and gcd(b^N-1 mod N,N).

Then nothing new would be learnt from gcd(a^N-1 mod N,b^N-1 mod N).

Or at least that's the way it seems to me.

David - I wrote (nonsensically):

> Then you should test gcd(a^N-1 mod N,N) and gcd(b^N-1 mod N,N).

This was rubbish, sorry. The new online reply facility is

> Then nothing new would be learnt from gcd(a^N-1 mod N,b^N-1 mod N).

seductive; must learn to think before I type!

I was mentally confusing this idea of Pavlos with

Marcel Martin's cunning way of factorizing pseudoprime

composites, which uses gcd(a^u-b^u mod N,N),

with u dividing N-1, as I recall.

David