Maths matters :: Euler's discovery about clocks with p x q hours  
         
     

If you take a time C on a clock with p x q hours on, how long does it take for C, (C x C), (C x C x C),… to repeat itself?

Euler discovered that the pattern repeats itself after (p-1) x (q-1) steps. So to get the original time one needs to raise C to the power (p-1) x (q-1)+1 or k x (p-1) x (q-1)+1 where k is the number of times one is repeating the pattern.

So to decode a message CE on this clock we must find a decoding number D such that E x D = 1 (modulo (p-1)x(q-1)) We have to do a calculation on a secret clock calculator with (p-1)x(q-1) hours. But a hacker only knows the numbers N and E. To find out the secret clock the hacker must uncover the secret primes p and q.

Cracking an internet code is the same as cracking a number N into its prime building blocks.

This is like looking at a pot of paint made from mixing two paints together and then trying to understand what colour paints were used to make the paint.

What are the best ways known to crack a number?
 
         

 

 
Home :: Prime importance :: $1,000,000 problem :: Maths matters :: The art of maths Copyright © 2003 Marcus du Sautoy