mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-04-17, 12:43   #1
smslca
 
Apr 2011

1112 Posts
Default modulo operation for polynomials?

I know , how to calculate " x mod p " for a given very large "x" value and some p value. Here , x and p are integers

But how can we calculate f(x) mod g(x) , for which f(x) has higher degree(or order) than g(x).
And that degree turns out to be a very large number.

Ex:[ (x+1)^1729 mod ((x^5)-1) ] or [ (x+1)^1729 mod (1729,((x^5)-1)) ]

Is there any method or algorithm to calculate it at faster speeds
smslca is offline   Reply With Quote
Old 2011-04-17, 13:21   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by smslca View Post
I know , how to calculate " x mod p " for a given very large "x" value and some p value. Here , x and p are integers

But how can we calculate f(x) mod g(x) , for which f(x) has higher degree(or order) than g(x).
And that degree turns out to be a very large number.

Ex:[ (x+1)^1729 mod ((x^5)-1) ] or [ (x+1)^1729 mod (1729,((x^5)-1)) ]

Is there any method or algorithm to calculate it at faster speeds
I would try this by finding the first exponent where (x+1)^y > (x^5)-1 find the mod there and then use floor(1729/y) as a power of that modulo and go from there the hard part for me is finding the first part with variable x.
science_man_88 is offline   Reply With Quote
Old 2011-04-17, 14:13   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110011002 Posts
Default

Polynomial division works just like integer division, except that each term is treated independently of all the others, so there are no carries from one term to the next. So modular exponentiation of polynomials can use the same algorithms as exponentiation of integers.

If the denominator polynomial is monic (i.e. leading coefficient is 1) then the remainder will always have degree less than the denominator. When an intermediate polynomial gets a coefficient of x^5, subtract that coefficient times the denominator polynomial. If the numerator has a leading coefficient x^k larger than x^5, pretend you're dividing integers and subtract off

(coefficient of x^k) * x^(k-5) * denominator(x)

to kill off the x^k term, then repeat with lower order terms until the remainder is less than the denominator.
jasonp is offline   Reply With Quote
Old 2011-04-18, 17:18   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jasonp View Post
Polynomial division works just like integer division, except that each term is treated independently of all the others, so there are no carries from one term to the next. So modular exponentiation of polynomials can use the same algorithms as exponentiation of integers.

If the denominator polynomial is monic (i.e. leading coefficient is 1) then the remainder will always have degree less than the denominator. When an intermediate polynomial gets a coefficient of x^5, subtract that coefficient times the denominator polynomial. If the numerator has a leading coefficient x^k larger than x^5, pretend you're dividing integers and subtract off

(coefficient of x^k) * x^(k-5) * denominator(x)

to kill off the x^k term, then repeat with lower order terms until the remainder is less than the denominator.
I have suggested repeatedly that anyone wanting to discuss computer
arithmetic or algebra be required to read Knuth Vol II before posting.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime numbers norms of modulo cyclotomic polynomials carpetpool carpetpool 24 2017-10-29 23:47
Operation: Billion Digits clowns789 Operation Billion Digits 574 2017-09-12 01:34
On polynomials without roots modulo small p fivemack Computer Science & Computational Number Theory 2 2015-09-18 12:54
Operation Megabit Twin Oddball Twin Prime Search 370 2013-01-03 21:26
The modulo operation, how is it computed? eepiccolo Math 7 2003-01-08 03:07

All times are UTC. The time now is 08:23.

Thu Dec 3 08:23:22 UTC 2020 up 4:34, 0 users, load averages: 1.19, 1.10, 1.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.