Query on DL

[R.D. Silverman]

Does anyone know how long the new Bos et.al. discrete log algorithm would take to solve
a single DL problem over (say) GF(2^1277)???

There is a reason for this query which I will reveal shortly.

[R.D. Silverman]

Originally Posted by R.D. Silverman

Does anyone know how long the new Bos et.al. discrete log algorithm would take to solve
a single DL problem over (say) GF(2^1277)???

There is a reason for this query which I will reveal shortly.

An Idea

Suppose we want to factor N = p^n-1, with p prime and n large.

Consider F = GF(p^n). Take a square S = s^2 in this field, and an integer b
coprime to p^n-1.

Compute the DL t of s^2 to the base b and hope that it is even.
We designate this as t = DL_b(s^2)

We have b^t = s^2 mod p^n-1 whence GCD(b^(t/2) - s, N)
splits N.

To factor p^n+1,, work over GF(p^(2n)). We "expect" that half the time
the GCD will split p^n+1 and half the time it will split p^n-1. ??????


Questions.

(1) What is the probability that s^2 is in the orbit of b, so that
the DL actually exists? Note that once we compute DL_b(s^2) changing base is
easy.

The probability is bounded above by 1/(2n). Its value is 1/(2n * pi^2/6)
This follows from the Carmichael function Lambda(N):
(Lambda = LCM(r-1, s-1), r-1, s-1 both divisible by 2n)

Therefore we should need to solve pi^2 n/3 = O(log N) separate DL problems to find a
value of S that works. This yields a run time of O(log N L(N, 1/4)) where N is the
standard L function. This may be practical if the Bos algorithm is fast enough. It is
asymptotically faster than NFS.


(2) What is the probability that t is even? If it is odd the method fails.
However, if t is odd it is possible to trivially change to a different base.
See below.

(3) For N = p^n+1, what is the probability that the GCD splits p^n+1, rather
than p^n-1?


Note that we can not take s^2 = 1. If N = rs with r,s prime, there is only
one Sylow subgroup of order r and one of order s. The odds that b will lie in one
of these subgoups is 1/r + 1/s. If b does not lie in one of these subgroups the DL
will maximal, i.e. p^n-1 and the factorization will be trivial. Finding an element
whose order is less than maximal will be nigh-to-impossible; one might as well try
trial division by randomly chose integers.

Note that the Bos algorithm makes computing the DL for such fields rather easy. L(N, 1/4) IIRC.


In case t is odd we can change the base b very easily.
Log_B(A) = log_b(A)/log_b(B) , therefore
Given log_b(s^2), we want log_c(s^2) so we copute log_b(s^2)/log_b(c)

The DL algorithm yields the log of all the factor base primes as one of its
outputs so there are lots of choices for the base change.



Comments? Please note that I do not have any DL software or I would try this myself.
Does Pari have a DL function and can it handle kilobit sized fields?

[tServo]

Originally Posted by R.D. Silverman

An Idea


Comments? Please note that I do not have any DL software or I would try this myself.
Does Pari have a DL function and can it handle kilobit sized fields?

Pari has 3 Discrete Log functions:
elllog, fflog, and znlog

My experience with Pari is that the main ( only? ) limitation on field size is your physical ram.
For instance, I have computed some megabyte-sized numbers.
Commands will need to be entered before computations begin to increase its allowed maximum ram usage.

[R.D. Silverman]

Originally Posted by R.D. Silverman

An Idea

Suppose we want to factor N = p^n-1, with p prime and n large.

Consider F = GF(p^n). Take a square S = s^2 in this field, and an integer b
coprime to p^n-1.

Compute the DL t of s^2 to the base b and hope that it is even.
We designate this as t = DL_b(s^2)

We have b^t = s^2 mod p^n-1 whence GCD(b^(t/2) - s, N)
splits N.

To factor p^n+1,, work over GF(p^(2n)). We "expect" that half the time
the GCD will split p^n+1 and half the time it will split p^n-1. ??????


Questions.

(1) What is the probability that s^2 is in the orbit of b, so that
the DL actually exists? Note that once we compute DL_b(s^2) changing base is
easy.

The probability is bounded above by 1/(2n). Its value is 1/(2n * pi^2/6)
This follows from the Carmichael function Lambda(N):
(Lambda = LCM(r-1, s-1), r-1, s-1 both divisible by 2n)

Therefore we should need to solve pi^2 n/3 = O(log N) separate DL problems to find a
value of S that works. This yields a run time of O(log N L(N, 1/4)) where N is the
standard L function. This may be practical if the Bos algorithm is fast enough. It is
asymptotically faster than NFS.


(2) What is the probability that t is even? If it is odd the method fails.
However, if t is odd it is possible to trivially change to a different base.
See below.

(3) For N = p^n+1, what is the probability that the GCD splits p^n+1, rather
than p^n-1?


Note that we can not take s^2 = 1. If N = rs with r,s prime, there is only
one Sylow subgroup of order r and one of order s. The odds that b will lie in one
of these subgoups is 1/r + 1/s. If b does not lie in one of these subgroups the DL
will maximal, i.e. p^n-1 and the factorization will be trivial. Finding an element
whose order is less than maximal will be nigh-to-impossible; one might as well try
trial division by randomly chose integers.

Note that the Bos algorithm makes computing the DL for such fields rather easy. L(N, 1/4) IIRC.


In case t is odd we can change the base b very easily.
Log_B(A) = log_b(A)/log_b(B) , therefore
Given log_b(s^2), we want log_c(s^2) so we copute log_b(s^2)/log_b(c)

The DL algorithm yields the log of all the factor base primes as one of its
outputs so there are lots of choices for the base change.



Comments? Please note that I do not have any DL software or I would try this myself.
Does Pari have a DL function and can it handle kilobit sized fields?

I had a blind spot. The required squares exist only when they are less than the
characteristic of the field! This doesn't work very well for characteristic 2.

Idiot.

[MacPrime]

Originally Posted by R.D. Silverman

I had a blind spot. The required squares exist only when they are less than the
characteristic of the field! This doesn't work very well for characteristic 2.

Idiot.

Ok, let‘s start with a simple example.

We want to factorize 7^3-1.

7^3-1 factorizes in Mersenne Prime exponents 2.3^2.19.

What do we learn from this?

342 is in the Mersenne-field.


When you have checked this, you are ready to go further.

[MacPrime]

Originally Posted by R.D. Silverman

I had a blind spot. The required squares exist only when they are less than the
characteristic of the field! This doesn't work very well for characteristic 2.

Idiot.

19936, which is 19937-1, is in the Mersenne-field as well.

19936 = 2^5.7.89

do you see the connections now?

[R.D. Silverman]

Originally Posted by MacPrime

Ok, let‘s start with a simple example.

We want to factorize 7^3-1.

7^3-1 factorizes in Mersenne Prime exponents 2.3^2.19.

What do we learn from this?

Nothing.

342 is in the Mersenne-field.

I have never heard the term "Mersenne-field". Please define it.

When you have checked this, you are ready to go further.

What is "this"? What is there to check?

[R.D. Silverman]

Originally Posted by MacPrime

19936, which is 19937-1, is in the Mersenne-field as well.

19936 = 2^5.7.89

do you see the connections now?

Gibberish. Please use standard notation.

What I suggested does work. Sort of. If one can find discrete logs quickly in
Z/NZ one can indeed factor N quite quickly.

One mistake that I made is that the fast DL algorithm of Bos et.al. does not work
in Z/NZ.

The Bos method works in GF(p^q).

Indeed, The only integers that exist in GF(p^q) must
be less than p. I.E. they must lie in the ground field. For GF(2^p) the only integers are 0
& 1.

One can't compute the DL of s^2 to the base b as I suggested because neither s^2 nor
b exist. As I put my presentation together I started by working in GF(p^q), but then
[confusion on my part; Idiot] started working in Z/(p^q-1)Z. There is no isomorphism
between the ring and the field. If one can find DL quickly in the ring one can indeed
factor p^q-1.

One should not do an ad hoc presentation in the manner that I did.