20110417, 12:43  #1 
Apr 2011
7 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 
20110417, 13:21  #2  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:


20110417, 14:13  #3 
Tribal Bullet
Oct 2004
DA1_{16} 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^(k5) * denominator(x) to kill off the x^k term, then repeat with lower order terms until the remainder is less than the denominator. 
20110418, 17:18  #4  
Nov 2003
1C40_{16} Posts 
Quote:
arithmetic or algebra be required to read Knuth Vol II before posting. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime numbers norms of modulo cyclotomic polynomials  carpetpool  carpetpool  24  20171029 23:47 
Operation: Billion Digits  clowns789  Operation Billion Digits  574  20170912 01:34 
On polynomials without roots modulo small p  fivemack  Computer Science & Computational Number Theory  2  20150918 12:54 
Operation Megabit Twin  Oddball  Twin Prime Search  370  20130103 21:26 
The modulo operation, how is it computed?  eepiccolo  Math  7  20030108 03:07 