mersenneforum.org Binary polynomial transformation modulo p
 Register FAQ Search Today's Posts Mark Forums Read

 2018-05-28, 21:09 #1 carpetpool     "Sam" Nov 2016 33510 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 2018-05-28 at 21:09
 2018-05-29, 01:14 #2 science_man_88     "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=16-2-1 but for x =2 it comes partially down to the binary represenation of p. Last fiddled with by science_man_88 on 2018-05-29 at 01:38
 2018-05-29, 13:43 #3 Dr Sardonicus     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 m-1. 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 well-known combinatorial problem, but I'm too lazy to look it up.
2018-05-29, 14:09   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts

Quote:
 Originally Posted by Dr Sardonicus The problem is trivial if a = 0, 1, or -1. We will henceforth assume that a is none of these. Thus, p > 3.
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.

2018-05-29, 17:38   #5
carpetpool

"Sam"
Nov 2016

1010011112 Posts

Quote:
 Originally Posted by Dr Sardonicus 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 m-1. 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 well-known combinatorial problem, but I'm too lazy to look it up.
Let p be a prime congruent to 1 modulo n where n is a prime. In GF(p), we are looking at the cyclic group generated by some element a with order n. There are a total of n elements in this group. The goal is to find at least three elements in G which sum to zero which should be possible for infinitely many primes p and n. That is beside the point though, what would matter is that we would need to find about 1 + floor(log(p)/log(2)) elements which sum to zero. Once this step is complete, the rest of this problem is a very simple discrete logarithm problem.

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^2-2*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^2-2*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^2-2*5, and 15-10 = 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.

 2018-05-29, 21:01 #6 carpetpool     "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 top-level: ...;for(i=1,154727,l=concat(l,g^i)) *** ^------- *** user interrupt after 30mins, 3,456 ms Of course, this is too infeasible, but what is interesting to me is if any algorithms exists which reduces the complexity time. Last fiddled with by carpetpool on 2018-05-29 at 21:01
2018-05-29, 21:21   #7
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by carpetpool Of course, this is too infeasible, but what is interesting to me is if any algorithms exists which reduces the complexity time.
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.

2018-05-29, 22:30   #8
carpetpool

"Sam"
Nov 2016

5·67 Posts

Quote:
 Originally Posted by science_man_88 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.
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).

2018-05-29, 23:41   #9
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts

Quote:
 Originally Posted by carpetpool 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).
Okay take it to linear algebra:
x^n+...+y=pz ;
The LHS is same parity as RHS which is determined by z.
Futhermore:
1. when x is odd, parity of the LHS depends on parity of number of odd coefficients and y.
2. when x is even, parity is determined solely by y.

 2018-05-30, 13:32 #10 Dr Sardonicus     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 degree-1 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.  I suddenly recalled that ternary (base-three) 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 base-three 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 2018-05-30 at 13:56
2018-05-30, 15:32   #11
carpetpool

"Sam"
Nov 2016

5×67 Posts

Quote:
 Originally Posted by Dr Sardonicus 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 degree-1 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.  I suddenly recalled that ternary (base-three) 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 base-three 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.
This would indeed indicate for a = 2, that p divides 2^n-1 (for whatever given p and n we are trying to use), similar for a = 3, it implies that p divides 3^n-1.

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(x-2,polcyclo(41)))%13367
%1 = 0
(08:18) gp > norm(Mod(x^14-x^11-x^10+x^6-x^3-1,polcyclo(41)))%13367
%2 = 0
Here is an example for base 3:

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(x-3,polcyclo(53)))%24169
%3 = 0
(08:23) gp > norm(Mod(x^9+x^8-x^7+x^4+x^3+x+1,polcyclo(53)))%24169
%4 = 0
(08:23) gp >
So the transformation from x - a to p(x) just implies that x - a and p(x) both share a common root of a modulo p. Of course, the problem becomes difficult when I asked for the smallest binary polynomial p(x) with fewest number of terms this is possible for.

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 14 2017-02-18 19:46 axn Computer Science & Computational Number Theory 66 2011-09-01 21:55 smslca Math 3 2011-04-18 17:18 Cyclamen Persicum Math 2 2003-12-10 10:52 eepiccolo Math 7 2003-01-08 03:07

All times are UTC. The time now is 00:20.

Tue Dec 6 00:20:45 UTC 2022 up 109 days, 21:49, 0 users, load averages: 0.43, 0.64, 0.72