Prev: Call for Papers: International Conference on Computational Biology ICCB 2010
Next: - Risto Lankinen -Packet Results <b>1</b> - <b>10</b> for <b></b>.
From: Risto Lankinen on 17 Jun 2010 04:52

Define sequence S:

S(0) = 1, S(1) = -1, S(n) =-2*(S(n-1)+S(n-2))
S = { 1,-1,0,2,-4,4,0,-8,16,-16,0,32,-64,64,0,-128,256,... }

Define table T:

T(x,y) = S(x+y)

Define square pattern:

1. T(0,0) contains a peg.
2. T(r,0) contains a peg if and only if T(0,r) contains a peg.
3. T(r,s) contains a peg if and only if both T(r,0) and T(0,s) contain
a peg.

- - -

Table T has the following property: Overlay some square pattern onto
table T. Add values of all cells in the whole table that contain a
peg
and call the result N. Add values of the cells on the first row only
that
contain a peg and call the result A . Then A is the average of some
pair of factors of N and factoring is now easy: D = SQRT(A*A-N) and
from that N = (A+D)*(A-D) .

The hard part, of course, is to find a non-trivial square pattern for
a given
(odd!) N . The whole mechanism resembles boolean logic based (as
opposed to numerical, or classical "mathematical") algorithm for
taking
a square root, and in fact I can demonstrate an algorithm that works
in
O(SQRT(N)) (where N is the composite) or O(EXP(n/2)) (where n is the
number of bits in the composite) steps. No better than trial
division,
I know, but can it be improved?

Cheers!

- Risto Lankinen -
 | 
Pages: 1
Prev: Call for Papers: International Conference on Computational Biology ICCB 2010
Next: - Risto Lankinen -Packet Results <b>1</b> - <b>10</b> for <b></b>.