mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-17, 18:20   #12
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·23·37 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
And, if number is small, the probability of beeing *smooth* much higher, isntly?
If we can find x^2 mod p~10^6 for RSA-260,270 and so on, do You think, this is do not help us to find the factors?
Yes, much smaller numbers would have a larger probability of being smooth. But so far we have not seen this from you, only ratios of 10^-1 to 10^-3 that are trivial to generate. So, show us a bunch of ratios of 10^-20, or those lists of x^2 mod p~10^6 for RSA-260,270.
bsquared is offline   Reply With Quote
Old 2021-02-17, 18:24   #13
charybdis
 
Apr 2020

3×7×11 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
Pari GP code
\p10000
{
p=2^8192+1;
Srp=sqrt(p);
for(m=1,1000,

x=m*2^4096;

B=lift(Mod(x^2,p));
localprec(5);
print(B/Srp/1.);
);
}
(x^2 mod p)/Sqrt(p)~10^1233
I do something wrong here???
...
To Mr. charybdis. The Signum x^2 mod p/Sqrt(p) must be + (Positive))))))
Negative values are fine because we can include -1 in the factor base. In this case we get (m*2^4096)^2 = m^2*(2^8192+1) - m^2, so this reduces to -m^2.

Quote:
And, if number is small, the probability of beeing *smooth* much higher, isntly?
If we can find x^2 mod p~10^6 for RSA-260,270 and so on, do You think, this is do not help us to find the factors?
Indeed. But by "small", I meant "around the size of sqrt(N)"; as I alluded to above, even 10^-20*sqrt(N) is out of reach with current techniques as far as I know. For RSA-260, it'll be difficult to find many values of x^2 mod N that are below, say, 10^120.

In practice, looking for the smallest possible values of x^2 mod N is not the most efficient way to proceed: it's about 10^5 times harder (I think!) to find such values around 10^-5*sqrt(N) than it is around sqrt(N), and they aren't 10^5 times more likely to be smooth, so there's no point in searching them out specifically. The best known factoring algorithm of this type is QS, which finds lots of values of x^2 mod N around sqrt(N) (or a little larger) in such a way that they can easily be sieved, allowing the smooth residues to be found quickly.

Last fiddled with by charybdis on 2021-02-17 at 18:25
charybdis is offline   Reply With Quote
Old 2021-02-17, 19:14   #14
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×23×37 Posts
Default

Quote:
Originally Posted by charybdis View Post
In practice, looking for the smallest possible values of x^2 mod N is not the most efficient way to proceed: it's about 10^5 times harder (I think!) to find such values around 10^-5*sqrt(N) than it is around sqrt(N)...
You are correct - I ran my QS poly generator in a loop and examined the smallest offsets near each root, gathering counts of values found that are smaller than sqrt(N). Here is example data for a 400 bit N (results are pretty consistent across a wide range of N sizes, dropping very slightly as N increases in size):


Code:
sqrtN = 8566463691637185710323259019755230896737522212231811895870570
found 80732629 small Q's (91.65 percent) with Q >= 1 bits below sqrtN
found 3701469 small Q's (4.20 percent) with Q >= 2 bits below sqrtN
found 1846974 small Q's (2.10 percent) with Q >= 3 bits below sqrtN
found 908506 small Q's (1.03 percent) with Q >= 4 bits below sqrtN
found 450578 small Q's (0.51 percent) with Q >= 5 bits below sqrtN
found 223450 small Q's (0.25 percent) with Q >= 6 bits below sqrtN
found 111367 small Q's (0.13 percent) with Q >= 7 bits below sqrtN
found 56011 small Q's (0.06 percent) with Q >= 8 bits below sqrtN
found 27932 small Q's (0.03 percent) with Q >= 9 bits below sqrtN
found 13859 small Q's (0.02 percent) with Q >= 10 bits below sqrtN
found 7074 small Q's (0.01 percent) with Q >= 11 bits below sqrtN
found 3436 small Q's (0.00 percent) with Q >= 12 bits below sqrtN
found 1792 small Q's (0.00 percent) with Q >= 13 bits below sqrtN
found 861 small Q's (0.00 percent) with Q >= 14 bits below sqrtN
found 402 small Q's (0.00 percent) with Q >= 15 bits below sqrtN
found 214 small Q's (0.00 percent) with Q >= 16 bits below sqrtN
found 102 small Q's (0.00 percent) with Q >= 17 bits below sqrtN
found 56 small Q's (0.00 percent) with Q >= 18 bits below sqrtN
found 20 small Q's (0.00 percent) with Q >= 19 bits below sqrtN
found 16 small Q's (0.00 percent) with Q >= 20 bits below sqrtN
found 11 small Q's (0.00 percent) with Q >= 21 bits below sqrtN
found 5 small Q's (0.00 percent) with Q >= 22 bits below sqrtN
found 4 small Q's (0.00 percent) with Q >= 23 bits below sqrtN
found 0 small Q's (0.00 percent) with Q >= 24 bits below sqrtN
So at 17 bits (Q is a factor 131072 smaller than sqrt(N)) we find roughly 10^5 fewer cases.

The data set only takes a few seconds to run, so it is pretty easy to find Q's a factor 1000 smaller. But as you said, these are far from 1000x more likely to be smooth.

Last fiddled with by bsquared on 2021-02-17 at 19:26 Reason: updated data set
bsquared is offline   Reply With Quote
Old 2021-02-17, 19:52   #15
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

23·5 Posts
Default

Whatever, I finding the sub sqrt values by iterations, and at least on the paper, there no difference between N^(1/2) or N^(1/3) or N^(1/4) or N^(1/u)=x^2 mod N. In real life, u=2 have solid convergence.u= 3,4 work nasty(mostly, do not work), time to time, and strongly depend on the initial guess values
RMLabrador is offline   Reply With Quote
Old 2021-02-17, 21:38   #16
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,391 Posts
Default

This thread is still not in Misc.Math?
Batalov is offline   Reply With Quote
Old 2021-02-18, 16:36   #17
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23×32×5×17 Posts
Default

Quote:
Originally Posted by retina View Post
To the OP.

Please just show us the process used to factor an RSA number.

As a starter I'll let you choose the number. But clearly show each step to arrive at p & q from n, without using knowledge of p & q as part of the process of course.
OP?

Do you have no example for us?

Does that mean you can't actually end RSA?

You could start with a really easy 20 digit number of your own construction. I left it wide open for you. If you can do that then we could see how it scales for larger, more practically sized, inputs.
retina is offline   Reply With Quote
Old 2021-02-18, 16:39   #18
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×1,117 Posts
Default

Suppose N = P*Q, the product of two (large) primes. The existence of small quadratic residues r (mod N) (that is, x2 == r (mod N) is solvable) isn't hard to prove.

If p is a prime not dividing N, there are 4 possibilities for the quadratic character values ((p/P), (p/Q)), namely

(+1, +1), (+1, -1), (-1, +1), and (-1, -1).

If p1, p2, p3, p4, and p5 are the smallest five primes which do not divide N, at least two of them, say pi, and pj, have the same quadratic characters (mod P) and (mod Q), so that r = pi*pj is a quadratic residue (mod P) and (mod Q).

Unfortunately, I don't see any easy way of figuring out which pair, or pairs, fill the bill.
Dr Sardonicus is offline   Reply With Quote
Old 2021-02-18, 23:27   #19
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

23×34 Posts
Default

@RMLabrador: Try factoring http://www.factordb.com/index.php?id...00002495591425 with your algorithm. I have the factors, but I won't submit them unless your algorithm is proven wrong/too slow.

Also, try 144122485282468744921 if the above is too hard.

Last fiddled with by Stargate38 on 2021-02-18 at 23:30 Reason: smaller example
Stargate38 is offline   Reply With Quote
Old 2021-02-19, 01:00   #20
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts
Default

Quote:
Originally Posted by charybdis View Post
For p = 2^8192+1, yes: just set x = m*2^4096. But those trivial examples end up providing the trivial factorization. Here's a non-trivial example:
Code:
x = 803712330813026779984467996238884416214971565156928364938627476528725619263969815396609420647192767387047088537280168342583133370289681466664036601515256664532162868492066319219259007761040628727765538023351930944192148126167775008808304629533263425355385253143896320528105897093057289903813911261509744364221596754349092599941773536171331556106296046599280481554646712992461892614349798233477965259877475138994405369825177696679729437587826887692542458552640942273034046406623315798263145680891043686637391445032540395910325375468851229335375596465691932642620033840048042340560874167717227536778565093687084864153161837295278248064251713015349610408163810844931599580893498289130468322100545342214765576626305162155916461392536927172939542370552699794841546639696942494594881295110745600057366133524417482823881185678378432601423479050253273048637028860317987716898476943479237944963468932359660280494291852550606787892845073491675204759474666914399743527694155136496340145306286054418911968297458076935976668197695596679564065649545218457256747009337097533753616066105580844244678581870354460484805422460891163318275126567016218201111245008239842784312223897326256240493829297074010128721808496403649817028179402655922067452553735272112935118098361819146571967747051042335555925523097129065280695181367968739521347020479123535829218438990155045578042788217027786532541928880255659048461964830031081904398973070429000057734538932753168313024384238767541247394456519521058254015485928934810784366724254324179715676652889973536367069586419264634867275009262773583800103905515266430450939923456449494611090021711359342468052239822729109374194303746299345611328064149077421843876123990868643886890836434434739760257148038097816243546053087649691162971380180235559659909995406227405187678476435360101478277900910234390714923447334131495658146877984060452350213335133741350913893372372382750661473520560745144219025403767567466795828619770559384086516426383867438230420766577174816679626762160826485843734576247890525078588673773345671323828967305229371643946636126423808174801397883494238901936327801483179139525127964756982777998986620463231000851111119178933344251128592435756253320495730367630320796405088860883924469265007923549271763392823093339083508933874249313935417311348420618482970064864798810442199766735648403349360198497005505625756767517663136001810083403724859580183756649673884657258679172071876388173521731691492002229655726374237582150646660585229025
gives
Code:
(x^2 mod p)/sqrt(p) = -0.00001411401799303015
In general, 10^-4 or 10^-5 is easy using continued fractions. 10^-20 isn't. But unless you can find a way of making these numbers more likely to be smooth, none of this will help you find the factors.
Actually it is easy, using the OP's other favourite number: F12 Fermat number [which was unfactored yesterday]:

Code:
N=2^4096+1;
x=694785161528292923786070190544555127232240209017636661869870533750882763489045000867332467054810239781399921579969506436642297683669911703872080967388500816022277746167694857580457652166225682974530552047112203051070338401109908446260279847078970792145467049257338313237868081366759136762565251648862281714914995197952316755064524338400918179455572546482880077018987683158318505298442798783267438375857916262236433095094292316209710672835987139312183549242253415226918092785089300407580368162509986228628720758163796878263167474617853571423652021277601746521663261163233388784562738278204035477697005166148741791444671221013316389071199405955489346962764911029066060952806706468840007209003757098020635429100939439790001980019741636794934562528612894292850402306119554279977156597950763874443170242820415159604620459350895817305168757436309593792476838456236394332656462170141068969911112855268986127446289522931510124437002265723783571727844109653361571149379210536707047831786919502836080940586269636140465448963287720825372805929802060293541140251875634166289176827612801578044851329006633310819343967394026364504199674632920414220663751847157995328508699229052114436701607271539306507184406826769097643090735334545700591255234078;
 
((x^2)%N)/sqrt(N)
%3 = 9.0460488930260020189274458788248289311 E-50

x/N*1.0
%4 = 0.66525522618374281552550148589689295545
?
Do you see, reached for the squared residue < 10^(-49)*sqrt(N), beating you all.
Where is my genious cheat?
R. Gerbicz is offline   Reply With Quote
Old 2021-02-19, 01:31   #21
charybdis
 
Apr 2020

3·7·11 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Actually it is easy, using the OP's other favourite number: F12 Fermat number [which was unfactored yesterday]:

...

Do you see, reached for the squared residue < 10^(-49)*sqrt(N), beating you all.
Where is my genious cheat?
Well yes, it does help that we already know 6 factors of F12
charybdis is offline   Reply With Quote
Old 2021-02-19, 01:53   #22
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

222428 Posts
Default

The small numbers not only have a higher probability to be smooth (like someone already pointed out), but they also have a higher probability to be squares (or powers, in general). If it is so easy to generate x^2 (mod p) to be as small as we want it, then make it to be two digits. There are 90 numbers below 100 which are not squares, so you only need to find 91 relations** to factor every N by difference of squares. No (quadratic) sieve needed, and no linear algebra. Piece of cake. Show us a factorization of RSA1024.

Edit: also, if making the values small is difficult, then please make the values be as close as possible to sqrt(N), in that case a method like Pollard rho will also find the factors reasonable fast.



---------
**in fact you need much less, as they also contain cubes and other odd powers (2^3, 3^3, 2^5) and you can easily combine them to eliminate multiples of 2, 3, primes, etc., and also, not all the numbers under 100 are quadratic residues. This works like the birthday paradox, except the birthdays are taken from 100, not from 365. So, maybe around 10 relations will always be enough (probabilistic) to find two with the same birthday? (no calculation done, wild ass guess). Then apply difference of squares, to factor any number, of any size.

Last fiddled with by LaurV on 2021-02-27 at 04:42
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Riesel Primes k*2^n-1, k<300 [Part II] Kosmaj Riesel Prime Search 1024 2021-04-11 17:38
I'm sure this is an ID-10-T error on my part petrw1 PrimeNet 1 2017-09-25 23:12
Numbers in Tables : Part 2 wustvn Puzzles 9 2007-12-31 05:14
Two PC's looking for part-time work OmbooHankvald Software 8 2005-07-23 01:23
Circles part 2 mfgoode Puzzles 10 2004-12-27 15:17

All times are UTC. The time now is 15:28.

Sun Apr 18 15:28:10 UTC 2021 up 10 days, 10:09, 1 user, load averages: 1.37, 1.38, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.