[ Home  |  FAQ-Related Q&As  |  General Q&As  |  Answered Questions ]

    Search the Q&A Archives

n=p*q where p,q are two large primes but I can find p and...

<< Back to: Cryptography FAQ (01/10: Overview)

Question by Duy Son
Submitted on 11/22/2003
Related FAQ: Cryptography FAQ (01/10: Overview)
Rating: Rate this question: Vote
n=p*q where p,q are two large primes but
I can find p and q if I know n
  
   for i=1:n
      if remainder(n/i)==0
          q=i;
          break;
      end
   end
      
  This I is my teacher's question . I can't answer satisfactory . Please help me !      


Answer by jmcqk6
Submitted on 11/29/2003
Rating:  Rate this answer: Vote
The point is, that takes an extremely long time.  Sure, You'll find a solution, or rather your machine will.  You'll be long dead by that point, and any information will no doubt be irrelevant.

 

Answer by OnyxBlack
Submitted on 6/16/2004
Rating:  Rate this answer: Vote
Right. it would take approximatly 10^12 years to find the factors p and q, if big primes were chosen. Besides, p and q might not be the only numbers (or primes, at that) wich result in n when multiplied. Your code would only check if the division leaves a remainder. It would break at the the first pair of numbers found. But who says that they are the key?

 

Your answer will be published for anyone to see and rate.  Your answer will not be displayed immediately.  If you'd like to get expert points and benefit from positive ratings, please create a new account or login into an existing account below.


Your name or nickname:
If you'd like to create a new account or access your existing account, put in your password here:
Your answer:

FAQS.ORG reserves the right to edit your answer as to improve its clarity.  By submitting your answer you authorize FAQS.ORG to publish your answer on the WWW without any restrictions. You agree to hold harmless and indemnify FAQS.ORG against any claims, costs, or damages resulting from publishing your answer.

 

FAQS.ORG makes no guarantees as to the accuracy of the posts. Each post is the personal opinion of the poster. These posts are not intended to substitute for medical, tax, legal, investment, accounting, or other professional advice. FAQS.ORG does not endorse any opinion or any product or service mentioned mentioned in these posts.

 

<< Back to: Cryptography FAQ (01/10: Overview)

[ Home  |  FAQ-Related Q&As  |  General Q&As  |  Answered Questions ]
© 2008 FAQS.ORG. All rights reserved.