three large primes

[xilman]

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.

[xilman]

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.

[henryzz]

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.

[CRGreathouse]

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.

[bsquared]

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).

[CRGreathouse]

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.

[bsquared]

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):

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.

[axn]

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?

[bsquared]

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

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.

[axn]

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

[chris2be8]

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