mersenneforum.org > Math modulo operation for polynomials?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-04-17, 12:43 #1 smslca   Apr 2011 710 Posts 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
2011-04-17, 13:21   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

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

 2011-04-17, 14:13 #3 jasonp Tribal Bullet     Oct 2004 67168 Posts 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.
2011-04-18, 17:18   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 24 2017-10-29 23:47 clowns789 Operation Billion Digits 574 2017-09-12 01:34 fivemack Computer Science & Computational Number Theory 2 2015-09-18 12:54 Oddball Twin Prime Search 370 2013-01-03 21:26 eepiccolo Math 7 2003-01-08 03:07

All times are UTC. The time now is 13:05.

Sat Jan 16 13:05:37 UTC 2021 up 44 days, 9:16, 0 users, load averages: 1.37, 1.62, 1.63