the tree of silence bears the fruit of peace

 

-Counsels and Maxims of Schopenhauer

diablo

 

the great equalizer

 

arcimboldo tributes

 

integer factorization reconsidered - trial multiplication

In nature, there is always a path of least resistance. Similarly, in math, there is always an optimal algorithm for any situation.

Regarding the integer factorization problem, only one case is of particular interest for cryptography: the factorization of large semiprimes when the prime factors are nearly equal. 

In this case, the most efficient method is to find the smallest integer n such that n^2 exceeds the semiprime. Any semiprime p*q will be less than some n^2 with p < n < q, and q << 2*n.

Suppose we want to factor 988027 and know it is semiprime. Its square root rounded to the nearest integer is 999. From trial multiplication, we find that 992 is the smallest integer that when squared is greater than 988027. And if we systematically check the numbers greater than 992 which end in 1, 3, 7, or 9, we quickly find that 997 is a factor of 988027. 

The semiprimes used for cryptography are vastly larger, but the principle is the same. It makes more sense to use trial multiplication before trial division. 

Trial multiplication is a method for solving the discrete logarithm problem. I see it as part of a one-two punch for the integer factorization problem. 

 

Rambo history lesson

Rambo in Afghanistan

I give Hollywood credit for trying to teach Americans world history via America's most famous fictional soldier. In Tanzania, where I lived for a few years, rambo is slang for a plastic bag, because most had his picture on it and they are tough like Stallone. 

Makmende is East Africa's version of Rambo and Chuck Norris. His name is joke on the Clint Eastwood phrase "make my day".

Just A Band - Ha-He

Sudden Impact - "Go Ahead Make My Day."

the big picture

Kurt Vonnegut sings the 53rd Calypso of Bokonan