Prev: Discrete logs result and degrees of freedom
Next: Ioncube php5 decoder
From: JSH on 30 Jun 2010 20:30
I've noted a way to solve discrete logarithms through factoring:

q^2 mod N

where with

f_1*...*f_m = q^2 mod N

you can find m simply enough from:

(k-1)*m = (f_1+...+f_c - c) mod N

where c is the count of factors in your factorization of q^2 mod N,
where prior posts explain from where the equations derive.

In a prior post I try to set an upper bound for q^2 mod N, which at
approximately 4N^2 is rather high, but there may be many reasons why
solutions will not approach that upper bound where I noticed one while
playing with small numbers, which is that the sum of the factors of
q^2 mod N, can be a constraining factor.

Consider 2^m = 60 mod 107. That gives f_1*...*f_m = q^2 mod N = 69
mod 107, and I've been adding N for my first try at a solution so
started with 176, which factors as 2*2*2*2*11, and those sum to give
19 but minus 5, I get 14, which may be close, but it's not right. So
I kept going, and quickly noticed that the sum of the factors were not
getting closer but *further* away.

Worrying a bit but knowing the underlying mathematics is solid, I went
back to 69, and finally noticed: 6+9-2 = 13.

2^13 = 60 mod 107

Intriguingly, with a larger prime relative to the answer, the factors
grew rapidly, so that the sum of the factors was way beyond m fairly
quickly, which forced early solution?

But still I'd think there'd be other answer with small primes. But of
course the math also has the ability to use a large m, which still
works, though it's not the smallest one that I'd prefer.
 | 
Pages: 1
Prev: Discrete logs result and degrees of freedom
Next: Ioncube php5 decoder