## 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.)