Combine sieving with SoB?

[akruppa]

>Do you think it would be a good idea to sieve the smooth prime numbers first and then the
>non-smooth?

It would speed up the rate of factors found, but bookkeeping will be a pain. And it will be a moot exercise when you start using P-1 before PRP testing, as P-1 will discover factors with smooth p-1 as well, so you'd get a lot of overlap between sieving and P-1. A much better solution would be an index-calculus DL for large prime factors of p-1, but it's a lot of work to write. Maybe look around on the net to see if anyone has a free implementation that suits your needs.

GNFS works on all numbers so long as they are not too large, say <150 digits. SNFS works if you can make two polynomials with small coefficients and common root modulo N. If by PSP numbers you mean numbers of the form k*2^n+1, then yes, these are well suited to SNFS, so long as k is not too large.

Alex

[Greenbank]

Thank you Alex for your explanations so far. From all of my searching you've provided the best examples that I have seen on the discrete log problem.

I'm trying to implement my own sieve, so I can better understand all of this. My sieve will never be as fast as the existing sieves but I want to implement one just for kicks.

So we can discard working on a k,p pair if and only if:-

Legendre(2,p) == 1 (i.e. p mod 8 is 1 or 7)
and Legendre(-1 p) * Legendre(k p) = 1

I'll probably have a few more questions regarding the other parts, I'm still playing with my implementation of Pohlig-Hellman and I've got a description of Index Calculus somewhere.

[akruppa]

>Legendre(2,p) == 1 (i.e. p mod 8 is 1 or 7)
>and Legendre(-1 p) * Legendre(k p) = 1

This condition is sufficient to discard a k,p pair, but not necessary.

A sufficient and necessary condition for discarding is:
if there exists a q^m | p-1, q prime, so that 2 is a (q^m)-th power and -1/k is not.

The reason is simply that there's no way to make a q^m-th non-power from a q^m-th power by exponentiating.

The quoted condition is merely the case q=2, m=1 simplified to use quadratic reciprocity instead of computing 2^((p-1)/2) and (-k)^((p-1)/2).

Alex

[Greenbank]

OK, I think I understand (thank you for your kind help so far!) let me try and write it down.

For each factor q of p-1 I compute:-

a = q^((p-1)/q) (mod p)
b = (-1/k)^((p-1)/q) (mod p)

I can discard if a=1 and b != 1. From the simple testing I've done it looks to hold as correct.

[Greenbank]

Originally Posted by akruppa

A much better solution would be an index-calculus DL for large prime factors of p-1, but it's a lot of work to write. Maybe look around on the net to see if anyone has a free implementation that suits your needs.

I've looked at the index calculus DL method and I can't see how it could be faster than BSGS or Pohlig-Hellman (or a hybrid of the two).

It would probably be faster if n were not bounded, but because n is bounded (to a relatively low value compared to p) then the other algorithms are faster.

Looking at a large p (such as 901561051768199), it could be a factor of k*2^n+1 as high as n=p-1. But we don't care about those n-values, we have set up an arbitrary limit of roughly n=80,000,000 (at least that's around the limit that proth_sieve throws out as factors when told to look for them up to 50M).

Here's a quick overview of the algorithm by example:-

This is from a PDF of a thesis. "On Factoring Integers and Evaluating Discrete Logarithms" by John Aaron Gregg. You should be able to google for that and find it.

Let p=307 and g=5. Suppose we are given y=214 and we will use IC-DL to find a such that g^a = y (mod p).

1. Pick random values for b and compute g^b (mod p).

(1) b = 30, g^30 mod p = 54 = 2*3^3.

2. Create a relation from the result:- 30 == L2+3*L3 (mod p-1)

Repeat with more random b values until enough relations have been built up that they can be solved with linear algebra:-

(2) b = 55, g^b = 120 = 2^3 * 3 * 5 -> 55 == 3L2 + L3 + L5 (mod p-1)
(3) b = 39, g^b = 128 = 2^7 -> 39 == 7 * L2 (mod p-1)
(4) b = 118, g^b = 175 = 5^2 * 7 -> 118 == 2L5 + L7 (mod p-1)
(5) b = 156, g^b = 182 = 2 * 7 * 13 -> 156 == L2 + L7 + L13 (mod p-1)
(6) b = 259, g^b = 198 = 2 * 3^2 * 11 -> 259 == L2 + 2L3 + L11 (mod p-1)

So,

L5=1 (because Lg=1)

(4) L7=118-2L5 = 118-2 = 116
(3) L2 = 39/7 (mod p-1) = 93.
(5) L13 = 156-L2-L7 = 156-93-116 (mod p-1) = 253
(2) L3 = 55-3L2-L5 = 55-279-1 (mod p-1) = 81
(6) L11 = 259-L2-2L3 = 259-93-162 = 4

So, L2=93, L3=81, L5=1, L7=116, L11=4, L13=253

3. Choose another random b such that (g^b)*y (mod p) has factors for which L value is known.

If we pick b=155 then, (g^b)*y = 176 = 2^4 * 11 (mod p)

4. It follows that, modulo 306, 155+a == 4L2+L11 == 4(93)+4 == 70.

a == 70-155 == -85 == 221 (mod p-1)

For verification:- 5^221 mod 307 = 214.

Now, applying it to base 2 with large p is quite tricky.

The problem is that values of b such that 2^b mod p are relatively smooth is very low. In a quick test program looking at p=901561051768199 (a factor for proth k=4847, n=2538111)

Out of 10000 random b values > 50 only 3 values (2^{560590,182210,409852}) were 997-smooth.

Of these three exponents, two had 8 unique factors and the other 7 unique factors.

If we only look at numbers that are 997-smooth then we would need at least 168 relations. (pi(997)=168). Even with the bare minimum number of relations it would be quite complex to solve the linear equations. 200 relations would be more useful. This would require evaluating, calculating and factoring around 67000 values.

If you compare this to BSGS with an upper bound of n of 80M then BSGS will be calculating sqrt(80M) values or around 9000 for the baby-step part, and another 9000 values for the giant-step part. Much less than the 67000 required for IC-DL.

This also doesn't take into account the time spent factoring (even up to 997-smooth it is quite considerable).

It also looks tricky because the modulo order of the group (Z/pZ)* may not be p-1. For example:-

g=2, p=1000033.

2^210118 = 3 (mod p) = 3

And, as expected:-

2^420236 = 9 (mod p) = 3^2

But:-

2^170228 = 9 (mod p) = 3^2
2^670224 = 9 (mod p) = 3^2
2^920252 = 9 (mod p) = 3^2

This is because the modulo order is 250008 (2^250008 (mod p) = 1) so (Z/1000033Z)* is partitioned into 4 seperate subgroups.

In the above example, in the PDF, the modulo order of base 5 mod 307 is 306. i.e. The smallest x such that 5^x == 1 (mod 307) is 306.

I'm not sure how easily it is to solve DL's with Index Calculus when the order of p is not p-1.

[akruppa]

Sorry for the long delay, I started reading Gregg's thesis but a few other things got in the way. I've read most of the thesis now (nice work!).

>It would probably be faster if n were not bounded, but because n is bounded (to a
>relatively low value compared to p) then the other algorithms are faster.

Good point. I was mostly worried that p where p-1 has a large prime factor would cause the GSBS algorithm spend a lot of time. But limiting the range for n effectively eliminates the problem.

In your example with p=901561051768199, the yield could be doubled by choosing the representant of smallest absolute value for the residues (i.e. -5 instead of 901561051768194) and allowing -1 into the factor base. I think your factor base may be a little on the small side as well, but that would depend on how fast the factoring algorithm is. Bernstein's "How to find small factors if integers" method might work well here...

I did some experiments as well and it looks like you'd need to test about 100000-150000 values of b before you get enough relations for a dependency. The three values you found among 10000 was atypically few. (The number of values to test in your example should be 670000, not 67000, right?)

Either way, looks like IC cannot compete with Pohlig-Hellman and BSGS if n is restricted to values <50M (or 80M or some such).

BTW, the fact that 2 may not be a generator of (Z/ZN)* should not be much of a problem. Choose a generator g, solve g^m==2 and g^n==k (the relations and matrix need to be done only once, and since 2 is trivially B-smooth, solving g^m==2 should be very easy). Then express (g^m)^(n/m) == 2^(n/m) == k, where the division n/m should be performed modulo p-1, i.e. by a modular inversion of m (mod p-1). This will only work if the denominator of the cancelled fraction n/m has no factor in common with p-1, which once again amounts to the condition that 2 must not be a power in Z/Zp that k is not.

Alex

[hhh]

I did some benchmarking on my laptop with

the SoB SoB.dat
the PSP SoB.dat and
a combined one of both.

Here are the numbers:

SoB: 367kp/s 30MB
PSP: 259kp/s 35MB
both:200kp/s 22MB

I used the 53000 range, open for both projects. The biggest dat used the less memory, don't know why.

The overall speedup will be even bigger (from a SoB-standpoint) when we reach the PSP-unsieved ranges and find all these first-pass factors.

So, I will try to do this range. I may take a while, but... If you are opposed, tell me, I will start only in a few days. (Of corse I don't put only this machine to work).

53000-54000 reserved hhh

[ltd]

For sure you can take this range.
With your test you have been a little bit faster then me.
I was thinking about doing something similar next week.
( But only with 1G as a test cause my main goal must be the catch up with
the SOB ranges).

I will transfer the reservation to the reservation thread.

Lars

[ltd]

@hhh:

When do you want to start your range ?
I can generate a new dat file short before you start if you want.

Lars

[Joe O]

Originally Posted by hhh

I
I used the 53000 range, open for both projects.
53000-54000 reserved hhh

Unfortunately, this range is currently being sieved by SoB. I don't know where you saw that it was open for SoB but it is not. Please email factrange at yahoo dot com for a reservation.
This is the official reservation database for the SoB low p effort

[hhh]

Ok, sorry, I take another one
53000 54000 unreserved
90000 91000 reserved by hhh
CU, H.