Loading ...
Sorry, an error occurred while loading the content.
 

Expand Messages
  • David Broadhurst
    ... 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
    Message 1 of 3 , Dec 30 4:05 AM
      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
    • David Broadhurst
      ... This was rubbish, sorry. The new online reply facility is seductive; must learn to think before I type! I was mentally confusing this idea of Pavlos with
      Message 2 of 3 , Dec 30 4:19 AM
        I wrote (nonsensically):

        > 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).

        This was rubbish, sorry. The new online reply facility is
        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
      Your message has been successfully submitted and would be delivered to recipients shortly.