20071025, 22:47  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Being coy about a factorisation
Suppose I claim to know the prime factors of
443010714176109914706062719399735837784888419454424993687966966355234791105604901627494851350770582163 and as evidence I tell you that 291423963431617699625266784773913140613841657204484201197140989542464400773582731403109417558223483732 119427483518486854181247739124795565127732359113308658130536891525701261106546136708919018267024127319 157520094591254666391292892953803503318347627033544019282262658910481182629167678068312685665643810948 239572651700526397232653310567005639418195632736211177608879033627897596067927907761541596172557189678 are the square roots mod N of 3, 7, 17 and 23 respectively. You can check my claim, but don't bother; it's true. Clearly, if I know the factors, I can compute the square roots. Clearly if you tricked me into giving you another square root of one of the primes you could compute the factors with probability 1/2. If I gave you the square roots of all the primes less than 10^10 mod N, you could do something like the quadratic sieve to recover the factors  find some T whose square mod N splits as a product of primes less than 10^10, check what I'd have claimed for the square root of that square, and with a good probability you can recover the factors by GCD. If I told you the quadratic character mod N of every prime less than 1000, you'd have a large number of modular constraints on the factors, and each constraint rules out half the numbers, so the ensemble of constraints gives you the factors; but dense Chineseremaindertheorem problems are hard to solve. But can you use just the four square roots I've given you to recover the factors? [this is not an interesting number, and now that I've closed the magma window I worked it out in I don't know the factors either, but running eight hours of GNFS to recover them is not in the spirit of the thing] 
20071101, 17:10  #2 
∂^{2}ω=0
Sep 2002
República de California
10110111101011_{2} Posts 
Hi, Tom: I probably haven't given this the consideration it deserves, but I don't see how the quadratic residuacity information you give can narrow things down more than via the standard approximatefactorof2foreachaddedQR. Is the fact that you provide actual explicit squarerootsmodulo [rather than just the QR which the finding of any square root demonstrates] meaningful?

20071101, 18:00  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Giving the square roots explicitly produces almost irrefutable evidence that I know the factorisation; you can check that what I've given is a square root of what I've claimed.
As far as I recall, the proof that SQRT is equivalent to factorisation is 'take random numbers M, square them, ask your SQRT oracle for the root, check GCD(rootM,N); the oracle can't know which M you gave, so with probability 1/2 will give a square root which is in the other class mod one of the primes'; this obviously doesn't apply in this situation, where I will remember which classes modulo the primes the sqrts that I gave you came from, and take care that I don't accidentally tell you something useful. 
20071101, 19:28  #4  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5·7·191 Posts 
Quote:
[1] That is not to say in the future a useful and quick algorithm could be found that can find the factors without GNFS Last fiddled with by retina on 20071101 at 19:29 

20071101, 19:39  #5  
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Quote:
But small primes really aren't arbitrary messages in this sense; you're not getting the kind of roundtrip that the proof requires. Could you suggest what kind of sample encryptions you'd be using to break RSA given an oracle for Nth roots of numbers less than 1000 ? Finding a number with a small enough or smooth enough cube is something of a feat without the factorisation. 

20071101, 20:05  #6 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5·7·191 Posts 
But the Rabin PKE uses squares. You've given square roots to prove you know the factors. The Rabin system also uses squared "encryptions" based upon the premise that finding square roots is equivalent to factoring in terms of computational difficulty of solving.
The Handbook of Applied Cryptography chapter 8.3 gives an explanation much better than I can do here. 
20071110, 04:30  #7 
Cranksta Rap Ayatollah
Jul 2003
641 Posts 
(this thread seemed worthy of an upgrade)

20071117, 01:27  #8 
Feb 2005
2^{2}·5·13 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factorisation  devarajkandadai  Factoring  7  20130706 03:44 
Records for complete factorisation  BrianE  Math  25  20091216 21:40 
Kraitchik's factorisation method  Robertcop  Math  2  20060206 21:03 