in [Theory]

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