cp's OEIS Frontend

A198512 Half the difference between an odd squarefree semiprime's factors.

%I A198512 #10 May 09 2013 22:34:18
%S A198512 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 A198512 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 A198512 28,9,1,20,31,10
%N A198512 Half the difference between an odd squarefree semiprime's factors.
%C A198512 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 A198512 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 A198512 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 A198512 Ehrhard Behrends, Five-Minute Mathematics, translated by David Kramer. American Mathematical Society (2008) p.s 25-26
%e A198512 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 A198512 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 A198512 (* First run the program for A046388 *) Table[(FactorInteger[A046388[[n]]][[2, 1]] - FactorInteger[A046388[[n]]][[1, 1]])/2, {n, 60}]
%Y A198512 Cf. A046388.
%K A198512 nonn,easy
%O A198512 1,2
%A A198512 _Alonso del Arte_, Oct 25 2011