Finding totient using discrete logarithm
 

I am posting this here because I think there might be a serious flaw with this technique. Given composite N, generator g, and prime q. find a generator g that is a primitive root to a composite N and some prime q. raise the generator to the power N. now (g^N) mod N = g^(N-totient(N)) mod N = k. Then mod the expression to a prime q so that g^(x mod totient(q)) mod q = k mod q. Now just solve for x and totient(N)= N-x Here is an example: (I am making these values and results up, they are not correct ) base=2, n=77,q=13. 2^77 mod 77 = 2^17 mod 77 = 19. 2^(17 mod 12)=19 mod 13=6. find the exponent by solving discrete logarithm 2^x mod 13 = 6. So the solution will be something like 5 or 5+12*x and one of the exponents should be correct (not in this case, I was to lazy to look up the correct calculations because my calculator died :(

[QUOTE=vector;118847]I am posting this here because I think there might be a serious flaw with this technique. Given composite N, generator g, and prime q. find a generator g that is a primitive root to a composite N[/QUOTE]

As with all proposals, reading stops at the first major mistake.

Composites do not have primitive roots.

I did not read the rest of your post.

I never knew that a composite modulus does not have any primitive roots. :blush:
Maybe this can be used to make a new deterministic primality test. (A prime is a provable prime if there is a primitive root mod the probable prime).
Anyway, I figured out that what was happening was just coincidence that occurs commonly for small numbers but almost never happens for larger moduli. So this discrete logarithm mod N lift to discrete logarithm mod P would never work.

:lol:

Sorry about that, but this is the exact basis for classical (you might almost say: ancient) deterministic primality tests that don't divide by all primes <= sqrt(P).

I.e. for the original P-1 primality test, you factor P-1 into primes p, then look for an element a so that a^(P-1) == 1 (mod P) but a^((P-1)/p) != 1 (mod P). This proves that p divides the order of a. If you do it for all p|P-1, you know the ord(a) = P-1, so it is a generator, so P is prime.

The Lucas-Lehmer tests works similarly, except you work in an extension ring and check that an element has order P+1 iff P=Mp is prime. The arithmetic in the extension ring is hidden by the use of Lucas sequences, so it still uses only arithmetic in Z/PZ.

Alex