May 2013
The intended solution was to factor 1+x+x^2+x^4 to (x^2+ax+b)(x^2+cx+d) modulo 2233393. Note that 2233393 = 19*41*47*61, so we can factor modulo each one of the four primes and combine the resulting coefficients using the Chinese remainder theorem. A possible answer is y=x*x a=638773*x a=y+a a=1613501+a b=1594620*x b=y+b b=b+1831287 z=a*b z=z mod 2233393
As for the bonus question - it's the June 2012 question from the UYHIP web site. Visit the site on July to learn about their solution.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com