mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-05-28, 21:09   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

33510 Posts
Post 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
carpetpool is offline   Reply With Quote
Old 2018-05-29, 01:14   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

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
science_man_88 is online now   Reply With Quote
Old 2018-05-29, 13:43   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

6,101 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2018-05-29, 14:09   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
science_man_88 is online now   Reply With Quote
Old 2018-05-29, 17:38   #5
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

1010011112 Posts
Post

Quote:
Originally Posted by Dr Sardonicus View Post
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.
carpetpool is offline   Reply With Quote
Old 2018-05-29, 21:01   #6
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5·67 Posts
Post

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
carpetpool is offline   Reply With Quote
Old 2018-05-29, 21:21   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
science_man_88 is online now   Reply With Quote
Old 2018-05-29, 22:30   #8
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5·67 Posts
Post

Quote:
Originally Posted by science_man_88 View Post
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).
carpetpool is offline   Reply With Quote
Old 2018-05-29, 23:41   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
science_man_88 is online now   Reply With Quote
Old 2018-05-30, 13:32   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

6,101 Posts
Default

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.

[Edit] 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
Dr Sardonicus is offline   Reply With Quote
Old 2018-05-30, 15:32   #11
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5×67 Posts
Post

Quote:
Originally Posted by Dr Sardonicus View Post
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.

[Edit] 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.
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46
Factorial modulo a prime axn Computer Science & Computational Number Theory 66 2011-09-01 21:55
modulo operation for polynomials? smslca Math 3 2011-04-18 17:18
N! modulo for large N Cyclamen Persicum Math 2 2003-12-10 10:52
The modulo operation, how is it computed? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔