Sunday, March 09, 2008

Fermat number factorization expressed as bits

log() denotes logarithm base 2.

log(2^32 + 1) =  9 +  23
log(2^64 + 1) = 18 +  46
log(2^128 + 1) = 56 +  72
log(2^256 + 1) = 50 + 206
log(2^512 + 1) = 21 + 162 + 328
log(2^1024 + 1) = 25 +  33 + 132 + 834
log(2^2048 + 1) = 18 +  20 +  67 +  72 + 1871

For F12 and F13, the final terms are still composite, 3942 and 7940 bits respectively. The .006 fractional part of the composite cofactor of F12 means that when it is written in binary it begins with seven zeros after the most significant bit: 100000001...

log(2^4096 + 1) = 17 +  25 +  26 +  37 +   50 + 3941.006
log(2^8192 + 1) = 41 +  61 +  62 +  88 + 7939.7997

F14 is still completely unfactored.

log(2n+1) = log(2n·(1+2-n)) = n+log(1+2-n) = n+ln(1+2-n)/ln(2) = (approximately, by Taylor expansion) n+2-n/ln(2). In order to express this small value 2-n/ln(2) in scientific notation, let x = log10(2-n/ln(2)) = log10(2-n)-log10(ln(2)) = -n·log10(2)-log10(ln(2)) = -n·ln(2)/ln(10)-ln(ln(2))/ln(10). For n=214=16384, this value is x = -4931.9162. Then, 10x/10-4932 = 10x+4932 = 100.0837 = e(0.0837·ln(10)) = 1.213.

So finally, we have log(216384+1) = 16384 + 1.213×10-4932 (The calculator bc only has ln and exp functions.)