mersenneforum.org > YAFU three large primes
 Register FAQ Search Today's Posts Mark Forums Read

2021-03-22, 19:10   #45
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

32·1,187 Posts

Quote:
 Originally Posted by henryzz 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.

2021-03-22, 19:12   #46
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

32·1,187 Posts

Quote:
 Originally Posted by bsquared 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.

2021-03-23, 08:00   #47
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts

Quote:
 Originally Posted by xilman 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.

2021-03-24, 00:43   #48
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by xilman 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.

2021-03-24, 02:37   #49
bsquared

"Ben"
Feb 2007

2×32×191 Posts

Quote:
 Originally Posted by xilman 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).

2021-03-24, 04:02   #50
CRGreathouse

Aug 2006

32·5·7·19 Posts

Quote:
 Originally Posted by bsquared 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.

2021-03-24, 13:31   #51
bsquared

"Ben"
Feb 2007

2×32×191 Posts

Quote:
 Originally Posted by CRGreathouse 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.

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

2021-03-24, 13:45   #52
axn

Jun 2003

2·13·191 Posts

Quote:
 Originally Posted by bsquared 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?

2021-03-24, 14:00   #53
bsquared

"Ben"
Feb 2007

2×32×191 Posts

Quote:
 Originally Posted by axn 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 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

2021-03-24, 14:52   #54
axn

Jun 2003

136616 Posts

Quote:
 Originally Posted by bsquared 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

 2021-03-24, 16:55 #55 chris2be8     Sep 2009 32×227 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Riesel Prime Search 3 2013-08-20 00:32 jasonp Msieve 24 2010-06-01 19:14 jasonp Factoring 4 2007-12-04 18:32 fivemack Factoring 18 2007-05-10 12:14 Prime Monster Lounge 34 2004-06-10 18:12

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

Sun May 16 00:52:05 UTC 2021 up 37 days, 19:32, 0 users, load averages: 1.80, 1.69, 1.71