 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 1112 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

203008 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 2·3·19·31 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.  Thread Tools Show Printable Version Email this Page 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 15:34.

Thu Jan 28 15:34:50 UTC 2021 up 56 days, 11:46, 0 users, load averages: 5.03, 4.25, 3.76