Prev: Wouldn�t It be Cool if These Were Equivalent?
Next: History of derivative of arithmetic function
From: master1729 on 30 Jun 2010 04:42
James Harris wrote :


> Here's an example, solve for m, where:
>
> 2^m = 13 mod 23
>
> so k = 2, and f_1*...*f_m = q^2 mod N = 13^2 mod 23 =
> 8 mod 23.
>
> And I found a solution with f_1*...*f_m = 54, and
>
> f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3
>
> so c=4, and
>
> m = (k-1)^{-1}(f_1 +...+ f_c - c) mod N = 2+3+3+3 - 4
> = 7
>
> And 2^7 = 128 = 13 mod 23.
>
> Notice that the method then gives you the number c
> from factoring
> numbers q^2 mod N. The means mathematically that c
> of the a's have
> been set by the algebra itself to cancel out k, with
> the modular
> inverse, which is how this approach eliminates the
> advantage of a
> large m--the math simply handles it for you.
>
> And that is the basic research showing how a simple
> set of modular
> equations can lead to an approach to solving discrete
> logarithms
> through integer factorization. It is not clear at
> this time how
> practical it can be made to be.

yes , how practical it is...

first , the method clearly works for

a^m = b mod p

a^2 =/= 0 =/= 1
m^2 =/= 0 =/= 1
b^2 =/= 0 =/= 1

and p an odd prime.

but the critics point out cases where the algoritm is not efficient.

so james - or anyone else - should wonder why that is possible ...

some advice from the master

basicly the algoritm can be slow BECAUSE it may not give the smallest possible solution , thereby even going slower than a brute force 1,2,3,4,... search.

so its a matter of finding the smallest possible solution.

its clear from the example below :

2^g+h = 2^g mod p

if and only if 2^h = 1 mod p

this logaritm of 1 got unnoticed because :

we cannot factor 1 into primes ! its not prime nor composite.

thus we need logaritm of 1 mod p.

so that is a big part of james his problem.

however !!

2^h = 1 mod p

2^(h-1) = 1/2 mod p

2^(h-2) = 1/4 mod p

and both 1/2 mod p and 1/4 mod p can be factored !!


regards

the master

tommy1729

" Cornacchia's algoritm is the best algoritm ever " tommy1729
 | 
Pages: 1
Prev: Wouldn�t It be Cool if These Were Equivalent?
Next: History of derivative of arithmetic function