Computer Algebra, Fall 2022, course documents

• We will look at this Maple worksheet on sequences in class.
• worksheet on polynomials and the use of the quotes: ' ' .
• worksheet on rational functions
• worksheet on modular arithmetic.
• Programming in Maple.
• Another introduction to Maple and some exercises to test yourself (in the form of a pdf-file) with some of the answers.
• The Euclidean Algorithm.
• Programming assignment: multiplication of polynomials.
• A sorting algorithm (called merge sort) based on the "divide and conquer" approach.
• Multiplying polynomials with the "divide and conquer" approach: the Karatsuba algorithm.

• Modular algorithms and the Chinese Remainder theorem.
• Study this program Modular algorithm for computing a determinant (don't worry about the complicated LinearAlgebra:-Modular commands, more important is to try to understand the overall setup; a bound B, a product m that should be at least 2B+1, and the chrem and mods(d,m) at the end). Here is an exercise for modular algorithms.
• The modular gcd algorithm. Read the worksheet The Extended Euclidean Algorithm.
• Study the algorithms in this worksheet and do the assignment about sqrfree. The worksheet explains how the following algorithms work:
  • The Extended Euclidean Algorithm (only implemented for the case of positive integers, but it works in the same way for polynomials).
  • How to do divisions modulo an integer p. Note: one can use a similar algorithm to do divisions modulo a polynomial.
  • How to compute quotients and remainders.
  • Euclidean Algorithm for polynomials.
  • Chinese Remainder Theorem (only implemented for two integer moduli m1,m2. Of course a very similar algorithm would work when m1,m2 are polynomials).
  • Do this assignment.
• Factoring in Fp[x].
• Short introduction to resultants.
• More details on resultants and an assignment.

• worksheet on p-adic numbers. For additional information see the worksheet on Factoring polynomials in Q[x] below.
• worksheet on x-adic Hensel lifting.
• Factoring polynomials in Q[x].

• Lattices
• implementation for dimension 2 (this does not generalize to higher dimension, for that, we need the paper of Lenstra, Lenstra, and Lovasz).
• General strategy for using LLL.
• Different way to factor in Q[x].
• Yet another example.
• Assignment
  m := 13^30; f1 := x^2+186754841457272102163578030635634*x+46880804142885485944842413874037;
  Find a polynomial g in Z[x] such that:
  • degree(g) < 8
  • coefficients of g have absolute values less than 300.
  • f1 divides g modulo m. So Rem(g, f1, x) mod m; is zero.
  • Quiz Oct 28. Copy/paste the following V into Maple:
  • V := [8922240876965072440870592126108241082611824828633565799931006581553112493921613791664068436735263769, 9352361050963951449874669224038442901629607449102634112380619791114587610749823100313511160300290177, 8609592101404110495833824566383159081849950298785326194467427747679155863910195625056624180362159464, 8913899690200659234040135401585349754002939234592932563210287929996751751533232822542972132630798950, -4906153829410084209912400653432596828900659888676763630075218887599162274087713613294674845102831170, -592775484852977374615357348790874076760846619071887397407734052869341066468104557924522121874595062, 1288294799640956317323689561459348123396382404953026984141904372342176225623898659007152152657604458, -5602098774918531150035343231324467385028656132686265803277266094594332071140498130704724384088334826, 8951651185189115358450055158865859062298556751752858171191241178213948167507470334884024224707656321, -9768459469572604838634684645820914604365422779571661666098726675495276657483695654846326783209634012, -6283420235104728902348633491131562969859502991863168411464685362587411470856339804206159739630418659, -8604025971275111361167944868496334860030632866918527472042627808227158828626243426244111073481995812, 88561539697946657701779027371179126777070600507954239355166428997522726493878219468901031456576697, -7297447000294045757379436220181888346014335420914444663862816139257814030876430003261588923268740960, -9742634278049127611404636739849524372914710076909615604020030787779497139515123789539279490112648893, 7199721955377033628659512181355340219246022628124412273210737257231815616157348213905646953754238541, 2242932357040745991188337785733728295792476780488553332337583629396155272498491056984463954989008827, -4707417639877498068711966497472228358749130240809610569516855134599743907128058529079874026318438323, -4829980384783232354414693546854178754550512573458949802506677330967942306737818739650239697281314990, -3048727391307598604570131111044163846949389777223077000686416276234523500827451606050591008357924356, -9373406649932613143662381261018573707416617990435018883116795764324804180757589135232563126913615635, -1382410204353455249658168150920682830536743785517297967935525879233967526809755327541666073540256020, -6819099289511055917235520293019329308308957038176722233520776488414107765716577669567658452985609258, -944613534159250547420662194567682712126361149489779720828806990500567869231157858076589989015708844, -1729368369847401720032834330207898342634339619681157351390328734579284615475889020101528690900143317, -3818959893465333838757900092148903155097342771985952071886218134169178352464858795569048665853380640, -7245854959226210989285067976448361814397786325384355689120682870253972444126975088329234156568423397, -1033152093497842139879118190051530230303470699804741918302010469103412609789061158277938474633565264, 7530273645760424351285901200340300104634486558996049558669078981845800389988056907655595707049727781, 3165677435350306699519749537865310573014509487830291429336274831182648765526736135404977120061623266, 8812647133145485492351423796907242644597037342318454027380508817852405748595126159652631285953474365, 1403792375742767321836884584823978154491471531980891449622607664916557988041805634512145911493072626, 7145720543912877347685300341485680348138385714562328336841884747331972016094473920592491480310680934, -2862162032257899024031112916506853107856398982059721537944331189482844721473075787635524264900931992, -8554363267978915971566980077289660758593789130290070731574046505693624711697406952625105641441231629, 8252847530824862884365044079031315962873323762001341622096024528901957221166578975875949377836106858, -9049487733289959943122183629115535738886967320049542168374964350973602936232655778694335120151206048, 224987700500540738624875945679789562818496986700206552969607708604376021985266401299308196875872182, 4150605511558929474890432555451407575346164289925403150378689107764754701241484494030876199775218504, -3306078131710646558517220765476414241034327887296120610178080331278960163961343700376505944201324431, 3638815078958083362642794928012765660607658417208858701102395309915527356781051536493160270289931023, 976622574210647194115478339788894283727135314196188088656670442680012736724047292024468247333293980, 4468919123249821263179834469322458769477180179973980280466575352654986635662775226079390451863529924, -3727097425856621969501330775825554257193038964354242366832849080681736202043688351247554183946081813, -8460959566522743624506285692238920145700175371078721498621908895239817911431071360390434957902103716, -7843333893940165115118249849676182842320655006888435649083707819225594805768070654806268617616295471, 4426713574321588239136211502883219358908793116447227889828037106976513511263251513917654473782524404, -8704149355694955722098460813037691812543756567615094203598705581024949759567514170105301858592747984, 7959839579399741355273508377882023127286207547524577654828985863832278165785984891258865262566935193, -5780906880460671952748855197847012018377875220959640944552561971122036278371162205102454511810930114, 3853252449369434050784502091341709370218251558966593502132496161344565773425671870016821624123506098, -8702200171439044018546632150331606040051373126636160165161988665163374978337523492229897561747736255, 6680848563676950410848144461004253587545280977983003800555054064460027445600459853285632918644738045, 8199764558264370432498093812974902469719066193297682763432475864621841395828046088041305178722828320, -8330632391645172847538923556352066489789514348257392668838815136206126443067586997310428822780093156, 3381663947210610823415442119647838457811691540863821371329997484825359457390817238620681542645981451, -3534872393282926997294082762208550569389420363420297005877016396670404169810044877124480613507100764, -7257880107903794427769654408640736806611953729344715331001781892341053057975107750485599503368543333, 62338322655644235590019742762898871223533166622672345673534753134332344466356604255437595127434314, -5356774168475214219010693450845527289680614202272043693092252995783400075826825118635025302573348324];
  • Find a sublist of V whose sum is 0, i.e. find a 0-1 vector e = [ 0 or 1, 0 or 1, .... ] in {0,1}^60 for which add(e[i] * V[i], i = 1..60) = 0.
  • Hint: You can create the k'th element of the standard basis like this: k := 4; v[k] := [0$(k-1), 1, 0$(60-k)];
  • Here is a text file that explains the basic notion of polynomial ideals and Hilbert's Nullstellensatz.
  • Solving polynomial equations, polynomial ideals: Groebner basis.
  • Applications of Groebner basis.
  • Assignments.
  • another assignment and two more
  Factoring Integers
  • Pollard's p-1 method for factoring integers
  • Elliptic curves
  Elementary integration