

A198512


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


0



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, 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, 28, 9, 1, 20, 31, 10
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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:
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.
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.


REFERENCES

Ehrhard Behrends, FiveMinute Mathematics, translated by David Kramer. American Mathematical Society (2008) p.s 2526


LINKS

Table of n, a(n) for n=1..60.


EXAMPLE

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
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


MATHEMATICA

(* First run the program for A046388 *) Table[(FactorInteger[A046388[[n]]][[2, 1]]  FactorInteger[A046388[[n]]][[1, 1]])/2, {n, 60}]


CROSSREFS

Cf. A046388.
Sequence in context: A278437 A175036 A177985 * A059573 A308437 A201283
Adjacent sequences: A198509 A198510 A198511 * A198513 A198514 A198515


KEYWORD

nonn,easy


AUTHOR

Alonso del Arte, Oct 25 2011


STATUS

approved



