|
%I #10 May 09 2013 22:34:18
%S 1,2,4,1,5,7,3,8,4,10,2,6,13,3,14,7,17,9,5,19,20,6,22,1,12,13,25,8,28,
%T 29,16,3,32,11,18,4,34,19,12,35,2,21,38,3,40,6,15,24,43,17,47,27,5,18,
%U 28,9,1,20,31,10
%N Half the difference between an odd squarefree semiprime's factors.
%C It is trivially easy to factor small semiprimes, even with trial division. But larger semiprimes can pose quite a challenge. Behrends (2008) gives a method cryptanalysts can use to factor a large semiprime that can work reasonably well if the prime factors, even if also very large, can be figured out if they are not spaced too far apart. The method exploits the following fact about odd semiprimes:
%C The square of half the difference between the prime factors, when added to the semiprime, gives a perfect square. The square root of that perfect square is halfway between the two prime factors of the semiprime. For example: 39 = 3 * 13, 13 - 3 = 10, 10/2 = 5, 39 + 5^2 = 64, sqrt(64) = 8, and lastly 8 - 5 = 3 and 8 + 5 = 13.
%C The method then is to add perfect squares to a suspected semiprime until finding another perfect square. In turn, cryptographers should choose large semiprimes with widely distant prime factors.
%D Ehrhard Behrends, Five-Minute Mathematics, translated by David Kramer. American Mathematical Society (2008) p.s 25-26
%e a(2) = 2 because the second odd squarefree semiprime is 21 and its two factors (3 and 7) are 4 apart, and 4/2 = 2
%e a(3) = 4 because the third odd squarefree semiprime is 33 and its two factors (3 and 11) are 8 apart, and 8/2 = 4
%t (* First run the program for A046388 *) Table[(FactorInteger[A046388[[n]]][[2, 1]] - FactorInteger[A046388[[n]]][[1, 1]])/2, {n, 60}]
%Y Cf. A046388.
%K nonn,easy
%O 1,2
%A _Alonso del Arte_, Oct 25 2011
|
