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

Carol/Kynea and PRP

Expand Messages
  • eharsh82
    Consider a number of this type n which is composite. suppose all the factors of n are known then a*b*c=n a,b,c 1 and the number has only 3 factors for
    Message 1 of 1 , Jan 22, 2004
    View Source
    • 0 Attachment
      Consider a number of this type n which is composite.
      suppose all the factors of n are known then a*b*c=n
      a,b,c>1 and the number has only 3 factors for simplicity reasons.

      gcd(a-1,b-1,c-1)= 2*m

      m in most cases will be 1 but can differ.
      if this is true then 2*m also divides n-1

      With that said it can be proven that there is a number h such that

      h^(2*m)-1 = 0 (mod n)
      h^(n-1)-1=0 (mod n)

      or n is a PRP for base h.

      An open question related to above:

      Given x,k and a prime p solve for a

      a^x= k (mod p)

      How would this be done? What algorithms can be used? What are there
      run times?

      Thanks,
      Harsh Aggarwal
    Your message has been successfully submitted and would be delivered to recipients shortly.