mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2021-03-22, 19:10   #45
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32·1,187 Posts
Default

Quote:
Originally Posted by henryzz View Post
Is there a reason why RSA-100 is so much slower?
My dad and I are currently working towards adding TLP to our SIQS implementation(record is C120 currently I think). The current target is ECM with Edwards curves. Is there a particular reason why you(and GMP-ECM) avoided Edwards curves?
Record for you, or record for anyone?

At least two groups, one of which included me, have done better than C130.
xilman is offline   Reply With Quote
Old 2021-03-22, 19:12   #46
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32·1,187 Posts
Default

Quote:
Originally Posted by bsquared View Post
I suspect because the rsa numbers were chosen to have poor QS factor base properties, but I haven't verified this.
I think this claim to be rather unlikely.

RDS has documented many times in many sources how he created the challenges. I have no reason to doubt his word that the constituent primes were chosen solely from the output of a true (i.e. hardware) random number generator.
xilman is offline   Reply With Quote
Old 2021-03-23, 08:00   #47
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10110111011102 Posts
Default

Quote:
Originally Posted by xilman View Post
Record for you, or record for anyone?

At least two groups, one of which included me, have done better than C130.
Personal best of course. This has been a many-year project with huge gaps in the middle.
henryzz is online now   Reply With Quote
Old 2021-03-24, 00:43   #48
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

Quote:
Originally Posted by xilman View Post
I think this claim to be rather unlikely.

RDS has documented many times in many sources how he created the challenges. I have no reason to doubt his word that the constituent primes were chosen solely from the output of a true (i.e. hardware) random number generator.
My feelings match Paul's.
CRGreathouse is offline   Reply With Quote
Old 2021-03-24, 02:37   #49
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·32·191 Posts
Default

Quote:
Originally Posted by xilman View Post
I think this claim to be rather unlikely.

RDS has documented many times in many sources how he created the challenges. I have no reason to doubt his word that the constituent primes were chosen solely from the output of a true (i.e. hardware) random number generator.
Sorry, I didn't mean that the numbers were constructed in some non-random way. I also do not doubt RDS's method. This is just me musing. RSA-100 *does* seem to be more difficult than other randomly chosen 100-digit semi-primes. Maybe several C100's were generated, and the one chosen was the most difficult of the lot (perhaps because it does not have a beneficial Knuth-Schroeppel multiplier available).
bsquared is offline   Reply With Quote
Old 2021-03-24, 04:02   #50
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by bsquared View Post
Sorry, I didn't mean that the numbers were constructed in some non-random way. I also do not doubt RDS's method. This is just me musing. RSA-100 *does* seem to be more difficult than other randomly chosen 100-digit semi-primes. Maybe several C100's were generated, and the one chosen was the most difficult of the lot (perhaps because it does not have a beneficial Knuth-Schroeppel multiplier available).
But that would be a non-random way (admittedly, one that would only allow a certain number of bits of non-randomness to be smuggled in), and I do doubt that this sort of trickery was used.
CRGreathouse is offline   Reply With Quote
Old 2021-03-24, 13:31   #51
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×32×191 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
But that would be a non-random way (admittedly, one that would only allow a certain number of bits of non-randomness to be smuggled in), and I do doubt that this sort of trickery was used.
Fair enough, I'll stop speculating.

So the answer to henryzz's question is that rsa-100 is slower because there is no good multiplier, and the factor base stinks. sum of log primes, p, for p < 1000, in the factor base for my random C100 is 496.9. sum of log primes, p, for p < 1000, in the factor base for RSA-100 is 394.2. I.e., significantly fewer small primes in the factor base. I guess this is just bad luck.

sum of log primes, p, for p < 1000, for 10 other randomly generated rsa-100's (using yafu's rsa() function):
Code:
461.0
557.6
478.3
446.6
522.0
481.9
494.9
488.4
466.2
434.8
Maybe the real answer is my rsa-generating function is faulty somehow. I followed section 4.4.2 in the handbook of applied cryptography and algorithm 4.53: Gordon's algorithm for generating strong primes.

[edit]
Generated 30 more to get a larger data set with mean sum(log(p)) of 496.9 and std of 36.99. So RSA-100 is about 2.7 standard deviations below the mean of this data set. Unlucky, but not extremely so.

Last fiddled with by bsquared on 2021-03-24 at 13:43 Reason: stats
bsquared is offline   Reply With Quote
Old 2021-03-24, 13:45   #52
axn
 
axn's Avatar
 
Jun 2003

136616 Posts
Default

Quote:
Originally Posted by bsquared View Post
Maybe the real answer is my rsa-generating function is faulty somehow.
Or the RSA100 is the outlier due to random luck? I believe you're over-interpreting a sample size of 1. Do any of the other RSA numbers (eg:- RSA110 or RSA120) have similar properties?
axn is offline   Reply With Quote
Old 2021-03-24, 14:00   #53
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×32×191 Posts
Default

Quote:
Originally Posted by axn View Post
Or the RSA100 is the outlier due to random luck? I believe you're over-interpreting a sample size of 1.
I'm sure I am

Quote:
Originally Posted by axn View Post
Do any of the other RSA numbers (eg:- RSA110 or RSA120) have similar properties?
RSA-110: 414.5 (multiplier: 3)
RSA-120: 482.6 (multiplier: 13)
RSA-130: 471.4 (multiplier: 1)

So, RSA-110 is 2.2 std below the mean. RSA-120 and RSA-130 are pretty close to the mean.

Last fiddled with by bsquared on 2021-03-24 at 14:00 Reason: fix quote
bsquared is offline   Reply With Quote
Old 2021-03-24, 14:52   #54
axn
 
axn's Avatar
 
Jun 2003

2×13×191 Posts
Default

Quote:
Originally Posted by bsquared View Post
So, RSA-110 is 2.2 std below the mean. RSA-120 and RSA-130 are pretty close to the mean.
Given this data (and the rest of the thread comments), I think it is reasonable to conclude that nothing special was done for RSA number generation in terms of QS-resistance. That's a long-winded way of saying, NTSHMA
axn is offline   Reply With Quote
Old 2021-03-24, 16:55   #55
chris2be8
 
chris2be8's Avatar
 
Sep 2009

32×227 Posts
Default

What is the first digit of RSA100 compared to your C100's? If it starts with 8 or 9 and yours mostly start with a smaller digit that would explain it. (I'm assuming they are all the same number of digits).

Chris
chris2be8 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where do I send my PRP primes with large k? Trilo Riesel Prime Search 3 2013-08-20 00:32
48-bit large primes! jasonp Msieve 24 2010-06-01 19:14
NFS with 5 and 6 large primes jasonp Factoring 4 2007-12-04 18:32
Why only three large primes fivemack Factoring 18 2007-05-10 12:14
What is the use of these large primes Prime Monster Lounge 34 2004-06-10 18:12

All times are UTC. The time now is 00:19.

Sun May 16 00:19:06 UTC 2021 up 37 days, 18:59, 0 users, load averages: 1.68, 1.64, 1.53

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.