20180528, 21:09  #1 
"Sam"
Nov 2016
335_{10} Posts 
Binary polynomial transformation modulo p
The Problem:
Given a modulo a prime number p, find the smallest binary polynomial (coefficients are either 1, 0, or 1) T (fewest number of terms), such that a is a root of T modulo p. Remark: This problem is the equivalent for discrete logarithm problems when a is a primitive root modulo p, when a isn't a primitive root modulo p, this problem becomes harder. Is there a known algorithm for completing this problem? Example: 2 modulo 19 Find P(x) such that 2 is a root of P(x) modulo 19. P(x) = x^d + x + 1 2^d + 2 + 1 = 0 modulo 19 2^d + 3 = 0 modulo 19 2^d = 3 modulo 19 2^d = 16 modulo 19 d = 4 modulo 19, d = 4, P(x) = x^4 + x + 1, hence 2 is a root of P(x) modulo 19: Harder problem: Given p = 37811769487424497663509746723 and a = 23759139709142185140061856193, find the smallest binary polynomial T (defined above) such that a is a root of T modulo p. Hint: a^184727 = 1 modulo p, meaning the highest degree that T can have is 184726. What's the first approach? Thanks for help. Last fiddled with by carpetpool on 20180528 at 21:09 
20180529, 01:14  #2 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
First thought on the problem is use basic math 18 mod 19 over 2 is 9 mod 19. So dropping everything down a degree gives us 9 mod 19 but still even aka 28 mod 38. Division by 2 gives 14 mod 19. Which can then be turned down to 7 mod 19. But still even = 26 mod 38 goes to 13 mod 19. 13=1621 but for x =2 it comes partially down to the binary represenation of p.
Last fiddled with by science_man_88 on 20180529 at 01:38 
20180529, 13:43  #3 
Feb 2017
Nowhere
6,101 Posts 
The problem is trivial if a = 0, 1, or 1. We will henceforth assume that a is none of these. Thus, p > 3.
If f(x) has coefficients 1, 1, or 0, so does f(x). Thus, there will be solutions for a and a of the same degree. There is a very simple proof that the minimum degree is no larger than 1 + floor(log(p)/log(2))  but, maddeningly, the proof is of little help in finding a solution. Consider the set of numbers a^k, k = 0 to m1. There are obviously 2^m sums formed by adding the members of subsets. If 2^m > p, there will be at least two distinct sums that are congruent (mod p). The difference of these two sums will produce a polynomial f(x) of degree at most m, with coefficients all 1, 1, or 0, and f(a) == 0 (mod p). Good luck finding them :( Trying to construct a solution appears to lead to a doubling at each step. Obviously, you want a polynomial divisible by x  a, say (x  a)*q(x). Under our assumption, the constant term is either 1 or 1. So the constant term of q(x) is either a^(1) or a^(1). Either choice leads to two possibilities for the coefficient of x in q(x). And, as you try to find the coefficient of x^2, you double your options again. You get a "tree" of possibilities with a number of "branches" that doubles at every step. I suppose that some of these "branches" might at some point terminate with unsolvable equations, but this approach does not look promising. I think this may be an instance of some wellknown combinatorial problem, but I'm too lazy to look it up. 
20180529, 14:09  #4 
"Forget I exist"
Jul 2009
Dartmouth NS
8418_{10} Posts 
It's also fairly trivial for a=2 because every number has a binary polynomial equivalent in base 2. a=3 has a possibly small solution possibility assuming the base 3 expansion doesn't have "12" in it.

20180529, 17:38  #5  
"Sam"
Nov 2016
101001111_{2} Posts 
Quote:
Suppose that there are no three elements in G which sum to zero. When considering the elements of GF(p), there should be exactly n^22*n distinct elements a such that either a^n=1 (a is an element in group G), or a is the sum of two distinct elements in group G. One could try using the given group G, find all the possible sums of distinct elements, then removing duplicates. If there are less than n^22*n elements, it means that there are three elements in G that sum to zero. Of course, we could expand the conditions higher, but I don't know how hard the computations and combinations would get. Here is a simple application of this: Consider p = 11, and n = 5. Then the group G contains the elements [1, 3, 4, 5, 9] (quadratic residues modulo 11) in GF(11). [1+1, 3+1, 4+1, 5+1, 9+1] = [2, 4, 5, 6, 10] [1+3, 3+3, 4+3, 5+3, 9+3] = [4, 6, 7, 8, 1] [1+4, 3+4, 4+4, 5+4, 9+4] = [5, 7, 8, 9, 2] [1+5, 3+5, 4+5, 5+5, 9+5] = [6, 8, 9, 10, 3] [1+9, 3+9, 4+9, 5+9, 9+9] = [10, 1, 2, 3, 7] So there are 10 elements in GF(11) which are either a quadratic residue, or sum of two distinct quadratic residues. Since 10 < 5^22*5, and 1510 = 5, this means there are at most 5 different ways that the sum of three quadratic residues is zero. Here is an example where it is not the case: p = 521, n = 5, the group G = [1, 25, 104, 396, 516]. [1+1, 25+1, 104+1, 396+1, 516+1] = [2, 26, 105, 397, 517] [1+25, 25+25, 104+25, 396+25, 516+25] = [26, 50, 129, 421, 20] [1+104, 25+104, 104+104, 396+104, 516+104] = [105, 129, 208, 500, 99] [1+396, 25+396, 104+396, 396+396, 516+396] = [397, 421, 500, 271, 391] [1+516, 25+516, 104+516, 396+516, 516+516] = [517, 20, 99, 391, 511] After removing duplicates and not counting the ones in red, then adding the original elements in G to the new list, we obtain a list with 15 elements in GF(521): [1, 20, 25, 26, 99, 104, 105, 129, 391, 396, 397, 421, 500, 516, 517] This implies that no three elements in G = [1, 25, 104, 396, 516] will sum to zero. 

20180529, 21:01  #6 
"Sam"
Nov 2016
5·67 Posts 
This PARI/GP script will also find the desired solution (or at least help find it) for the given case:
t = 37811769487424497663509746723 s = 23759139709142185140061856193 g=Mod(s,t) l=[]; for(i=1,154727, l=concat(l,g^i)) for(i=1,154727, for(j=1,154727, for(k=1,154727, for(m=1,154727, for(p=1,154727, for(q=1,154727, for(r=1,154727, if(l[i]+l[j]+l[k]+l[m]+l[p]+l[q]==l[r], print(i*x+j*x^2+k*x^3+m*x^4+p*x^5+q*x^6+r*x^7))))))))) Code:
(13:56) gp > t = 37811769487424497663509746723 %14 = 37811769487424497663509746723 (13:58) gp > s = 23759139709142185140061856193 %15 = 23759139709142185140061856193 (13:58) gp > g=Mod(s,t) %16 = Mod(23759139709142185140061856193, 37811769487424497663509746723) (13:58) gp > l=[]; for(i=1,154727, l=concat(l,g^i)); < for(m=1,154727, for(p=1,154727, for(q=1,154727, for(r=1,154727, if(l[i]+l[j]+l[k]+l[m]+l[p]+l[q]==l[r], print(i*x+j*x^2+k*x^3+m*x^4+p*x^5+q*x^6+r*x^7))))))))) *** at toplevel: ...;for(i=1,154727,l=concat(l,g^i)) *** ^ *** user interrupt after 30mins, 3,456 ms Last fiddled with by carpetpool on 20180529 at 21:01 
20180529, 21:21  #7 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
If we knew if it was an odd multiple or even multiple we could optimize maybe to equal an odd multiple it can only have an odd number of non zero terms (including constant term) if even multiple only an even number of non zero terms should work.

20180529, 22:30  #8 
"Sam"
Nov 2016
5·67 Posts 
We are working with the system of integers modulo some odd prime p, so even/odd doesn't exist in the finite field GF(p).

20180529, 23:41  #9  
"Forget I exist"
Jul 2009
Dartmouth NS
20342_{8} Posts 
Quote:
x^n+...+y=pz ; The LHS is same parity as RHS which is determined by z. Futhermore:


20180530, 13:32  #10 
Feb 2017
Nowhere
6,101 Posts 
My analysis of trying to construct a solution was overly optimistic. The choices for coefficients are 1, 0, or 1. So (assuming a is not 1, 0, or 1, and p > 3) we may assume a solution
p(x) = (x  a)*q(x) has nonzero constant term, so the constant term of q(x) is a^(1) or a(^1) (mod p). For the degree1 and higher coefficients, though, there are three possible choices. science_man_88's solution for a = 2 (use the binary expansion for p to base two) looks tough to beat. It gives a polynomial of degree just one less than my universal degree bound m = 1 + floor(log(p)/log(2) = least integer such that 2^m > p. So, absent some way to eliminate candidates wholesale, or construct a solution directly, it looks like at least O(p) calculations. [Edit] I suddenly recalled that ternary (basethree) expansions with the usual digits 0, 1, and 2 can be modified using 2*3^k = 3^(k+1)  3^k (repeated as necessary) to express any positive integer as a sum powers of three, multiplied by coefficients 0, 1, or 1. This has been known for a long time, and applied to weighing problems. At worst, the new expression will involve a power of three one greater than the original basethree expression, e.g. 2*3^0 = 3^1  1 or 2*3+2 = 3^2  1. So for a = 3, there is a solution of degree at most 1 + floor(log(p)/log(3)) which can be constructed directly. Last fiddled with by Dr Sardonicus on 20180530 at 13:56 
20180530, 15:32  #11  
"Sam"
Nov 2016
5×67 Posts 
Quote:
Here is a quick example: p = 13367  2^41  1 13367 = 2^14  2^11  2^10 + 2^6  2^3  1 p(x) = x^14  x^11  x^10 + x^6  x^3  1 Code:
(08:18) gp > norm(Mod(x2,polcyclo(41)))%13367 %1 = 0 (08:18) gp > norm(Mod(x^14x^11x^10+x^6x^31,polcyclo(41)))%13367 %2 = 0 p = 24169  3^53  1 24169 = 3^9 + 3^8  3^7 + 3^4 + 3^3 + 3 + 1 p(x) = x^9 + x^8  x^7 + x^4 + x^3 + x + 1 Code:
(08:23) gp > norm(Mod(x3,polcyclo(53)))%24169 %3 = 0 (08:23) gp > norm(Mod(x^9+x^8x^7+x^4+x^3+x+1,polcyclo(53)))%24169 %4 = 0 (08:23) gp > As Dr. Sardonicus said this might be an instance of some combinatorial problem. I will look more into this and post if I see something. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Discriminant is n^k for an n1 degree polynomial  carpetpool  Miscellaneous Math  14  20170218 19:46 
Factorial modulo a prime  axn  Computer Science & Computational Number Theory  66  20110901 21:55 
modulo operation for polynomials?  smslca  Math  3  20110418 17:18 
N! modulo for large N  Cyclamen Persicum  Math  2  20031210 10:52 
The modulo operation, how is it computed?  eepiccolo  Math  7  20030108 03:07 