20090113, 18:06  #1 
Jan 2005
Minsk, Belarus
2^{4}×5^{2} Posts 
Lucaslike sequence of polynomials: a tricky thing
Somewhere in 2001 I tried to improve a LucasLehmer test, doing several iterations at once. So, if we have x as an intermediate result, we obtain
x^{2}2 x^{4}4x^{2}+2 x^{8}8x^{6}+20x^{4}16x^{2}+2 and so on. I did some calculations by hand (I was on holiday in a countryside and had no computer) and noticed that the coefficients of every polynomial could be easily factored. I conjectured a very surprising and tricky general factorization of these coefficients, involving such strange things as the number of units in binary representation, etc: http://www.primefan.ru/stuff/primes/polynomials.pdf E.g., the polynomial of degree 256 has the following coefficients: http://www.primefan.ru/stuff/primes/256.txt With a computer I checked this formula up to high powers and found no counterexample. In Nov 2002 I asked the PrimeNumbers Yahoo! group about that but with no success: http://tech.groups.yahoo.com/group/p...s/message/9577 In Jan 2003 I tried to ask the NMBRTHRY community but my email was rejected. The same file "polynomials.pdf" is still lying in the Articles subfolder of the Files section of PrimeNumbers Yahoo! group since that time: http://tech.groups.yahoo.com/group/p...iles/Articles/ Recently I digged up this stuff and decided to post it there. Maybe something is already known about these tricky factorizations of the polynomial coefficients? Last fiddled with by XYYXF on 20090113 at 18:36 
20090114, 01:26  #2 
Feb 2006
Denmark
E6_{16} Posts 

20090114, 05:31  #3  
Jan 2005
Minsk, Belarus
2^{4}·5^{2} Posts 
Quote:
http://tech.groups.yahoo.com/group/p...s/message/9577 My coefficients should come from the triangle http://www.research.att.com/~njas/sequences/A108045 I see some relations to binomial coefficients in your link; will try to prove my conjecture using this... :) Last fiddled with by XYYXF on 20090114 at 05:35 

20090114, 17:25  #4 
Aug 2006
13533_{8} Posts 
Well, the number of squarings is already optimal, so at best you'd be reducing the number of additions. Since the additions are (with probability around 1  2*2^(limb size), or about 99.99999995% for 32 bits) likely to involve only 1 limb, your savings are bounded above (in the average case) by about twice the exponent in cycles. For exponents around 10^8, that would be 100 ms on a 2 GHz chip.

20090130, 11:31  #5 
Feb 2004
France
3^{2}·103 Posts 
Rather consider:
S(0)=2 S(1)=x S(2)=x^{2}2 S(3)=x^{3}3x and so on. where S(n) = x S(n1)  S(n2) Tchebitchev. This is related to the LLT. T. Last fiddled with by T.Rex on 20090130 at 11:42 
20090311, 17:20  #6  
Feb 2005
FD_{16} Posts 
Quote:
Polynomials are elements of Lucas sequence , namely: which can be also expressed as Chebyshev polynomial: An explicit formula for the coefficients of Chebyshev polynomials is given in http://www.research.att.com/~njas/sequences/A053120 The "main" term of this formula is the binomial coefficient . Applying Lucas theorem to it, one can express this binomial coefficient as the product of "maximal powers of p ... equals to the number of positive integers m's satisfying inequality", similarly to how you defined . This way you can derive and prove your formula for . Last fiddled with by maxal on 20090311 at 17:23 

20100826, 21:46  #7  
Jan 2005
Minsk, Belarus
2^{4}·5^{2} Posts 
maxal, thanks you a lot, all is clear now.
Quote:
http://www.primefan.ru/stuff/math/polynomials.pdf http://www.primefan.ru/stuff/math/256.txt 

20100827, 11:52  #8  
Nov 2003
2^{2}·5·373 Posts 
Quote:
in fact the orbit of an element of the twisted subgroup of GF(P^2). The twisted subgroup is the set of elements whose multiplicative inverse equals their algebraic conjugate. Note that the formula for P_n above equals z^2^n + z' ^2^n where z and z' are in fact algebraic conjugates and also note that they are multiplicative inverses. z and z' are elements of the twisted group. What the Lucas Lehmer test for M_p really does in a sense is to show that the analogue of 'primitive root for p in Z/pZ*' exists in the group whose order is p+1, not p1. Why p+1 and not p1?? Because for P = 2^n1 we know the complete factorization of P+1. The Lucas Lehmer test is really only exponentiating an element of the twisted group and showing that it has the correct order. The recurrence relation x_n = x_{n1}^2  2 happens to have a simple formula for x_n in terms of z and z'. BTW, it is this same formula that makes x^22 a very poor choice of polynomial for Pollard Rho. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Tricky constant acceleration question  lavalamp  Puzzles  29  20091214 15:27 
Period of Lucas Sequence modulo a prime  T.Rex  Math  7  20070604 21:30 
A tricky way to estimate pi(x)  XYYXF  Math  13  20060901 15:44 
Tricky differentiaton 1  mfgoode  Puzzles  16  20060125 16:32 
Tricky Problem with AMD 3700+  pseudorandom  Hardware  11  20060123 08:53 