<Text-field style="Heading 1" layout="Heading 1"><Equation executable="false" style="Heading 1" input-equation="" display="LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2I1EhRicvJSdmYW1pbHlHUTBUaW1lc35OZXd+Um9tYW5GJy8lJXNpemVHUSMxMkYnLyUlYm9sZEdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYn">JSFH</Equation>Introduction</Text-field>

CS 487/687 CM 730: Introduction to Symbolic Computation

Winter 2023

Instructor: Arne Storjohann <astorjoh@uwaterloo.ca>

This course is an introduction to the use of computers for symbolic mathematical computation, commonly called computer algebra.

The types of mathematical computations of interest include

simplifying rational expressions

factoring polynomials

solving linear equations

solving polynomial equations

integration of functions

solving recurrences

factoring integers and proving primality

...

The course is designed to expose students to:

the design and analysis of algorithms for algebraic problems;

the concepts from modern algebra which are applied to the development of algorithms for symbolic computation

the programming languages and data structures used for symbolic computation; and various applications of symbolic computation.

JSFH

<Text-field bookmark="Symbolic Mathematical Computation" style="Heading 1" layout="Heading 1">Symbolic Mathematical Computation</Text-field>

JSFH

In other words: How do we do mathematics on a computer?

rnd:=rand(0..10^19):

a:=rnd(); b:=rnd();

a+b;

a*b;

a^100;

JSFH

<Text-field bookmark="Solving Linear Systems of Equations Exactly" style="Heading 1" layout="Heading 1">Solving Linear Systems of Equations Exactly</Text-field>

How d

o we solve systems of equations exactly?

with(LinearAlgebra);

n:=5;

A:=RandomMatrix(n,n);

b:=RandomVector(n);

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

LinearSolve(A,b);

B:=A[1..n,1..n]: B[1..n,1]:= b: Determinant(B)/Determinant(A);

What if A[3,3]=x and A[4,5]=y?

A[3,3]:=x;

A[4,5]:=y;

LinearSolve(A,b);

map(normal,%);

What if n=100?

A:=RandomMatrix(100,100);

b:=RandomVector(100);

LinearSolve(A,b);

%[1];

<Text-field bookmark="Factoring" style="Heading 1" layout="Heading 1">Factoring Polynomials</Text-field>

Consider the problem of factoring polynomials

This is pretty fundamental: it takes a large problem and breaks it into smaller ones

f:=x^23-x^16-2*x^13+3*x^20-2*x^10+2*x^11-2*x^4+2*x+5*x^3-5;

factor(f);

How do we go about performing this operation?

How do we represent the polynomials in question?

How much does this cost?

Sometimes it is easier to use a "modular algorithm"

Compute modulo small primes, then "reconstruct" the integer or rational solution

This will be a standard approach.

For example, start by factoring

f modulo a small prime p.

p:=13;

Factor(f) mod p;

Looks a bit weird (where did all those factors come from), but it will help.

What about a "fancier" f:

f:=x^3*y^2+x^6-3*x*y^3-3*x^4*y+15*x*y+5*y^2-25;

factor(f);

NextLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

<Text-field style="Heading 1" layout="Heading 1">Solving Polynomial Equations</Text-field>

In many applications, we often have a collection of multivariate polynomials

f:=-x*y^2-3*x*y;

g:=2*x^2+4*x*y+y^2;

plot3d([f,g],x=-2..2,y=-2..2,color=[blue,green]);

solve(f=g);

solve({f=0,g=0});

We will (start to) explore the techniques use to solve these systems of polynomial equations.

<Text-field bookmark="Number Theory" style="Heading 1" layout="Heading 1">Computational Number Theory</Text-field>

Some important operations with integers are "hard" (at least in one direction) which makes them very useful.

Consider the problem of multiplying and factoring integers.

Multiplying integers is pretty straightforward (though there are ways to do better)

a:=nextprime(2^85); b:=nextprime(a); n:=a*b;

We can check if

n; is prime (it better not be):

isprime(n);

We can also attempt to factor n:

ifactor(n);

Hmmm: that seems to take a bit longer...

The difficulty of algorithms for factorization and related operations is the foundation on which much of modern cryptography rests.

How hard are these problems and why?

<Text-field bookmark="Course Focus" style="Heading 1" layout="Heading 1">Focus of CS 487/687</Text-field>

Algorithm design and analysis

<Text-field style="Text" layout="Heading 2">Computer science</Text-field>

fundamental algorithm design for algebraic problems

careful analysis of these algorithms, counting "real" computational cost, and also more abstract notions (like counting field and ring operations)

efficient implementation (sequentially here)

computer algebra system use and design

applications

<Text-field style="Text" layout="Heading 3">Mathematics</Text-field>

More algebra than analysis (at least in this course)

Mathematics not terribly difficult, but we may use it in unusual ways

Brush up on your Math 135 (Algebra),, Math 136 (Linear Algebra) and Math 239 (Combinatorics)

We will also get familiar with some modern computer algebra systems (mostly Maple)

<Text-field bookmark="Course Operations" style="Heading 1" layout="Heading 1">Course operations</Text-field>

Take a look at the course website: http://www.student.cs.uwaterloo.ca/~cs487

This is your primary source of information.

You are responsible for keeping up-to-date with current course events through this site.

I will keep it updated with the latest information.

Let's go there now.

JSFH

We will use Piazza. Not been set up yet... maybe in a week.

Ask general questions, and please be careful not to post solutions!

Handouts

Handouts will be posted on the website as a combination of typeset notes, slides, Maple worksheets and other code

You are encouraged to execute and experiment with all examples and code

Some material will only be given in class

Marking Scheme CS487

Final Exam 40%

Midterm Exam 25%

Assignments 35%

Marking Scheme CS687

Final Exam 30%

Midterm Exam 20%

Assignments 30%

Project 20%

Midterm Exam

Proposed date: TBA, in class

Assignments

Around 5 Assignments, combination of algorithm development, analysis, and coding

This is not a course in Maple, Sage, C++, Python, etc. You will be expected to pick up the necessary coding skills in appropriate languages

CS687 Projects

A list of possible CS 687 potential will be posted in February

Students are encouraged to come up with their own project (related to the course topics)

<Text-field bookmark="Topics" style="Heading 1" layout="Heading 1">Topics</Text-field>

Some topics we will hopefully cover in CS487/CS687 are the following:

Representation and basic arithmetic in algebraic domains (extended integers, polynomials)

Division with remainder.

GCD and the extended euclidean algorithm.

Solving integer linear equations.

Modular computation.

Evaluation/Interpolation and the Chinese remainder algorithm.

Rational system solving (Gaussian elimination vs. p-adic lifting)

Fast arithmetic: multiplication and division.

Newton iteration in algebraic domains.

Factoring polynomials over finite fields.

<Text-field bookmark="Fundamental Ops" style="Heading 1" layout="Heading 1">Representation of multi-precision integers</Text-field>

Will follow von zur Gathen & Gerhard text: Chapters 2 and 3, and sections of Chapters 4 and 5.

Current computers are based on architecture with 32- or 64-bit bus and words

let's assume the word size is 64 bits

e.g. "unsigned long" in C can represent integers exactly in range

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNistSSNtbkdGJDYkUSIwRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLUkjbW9HRiQ2LVEjLi5GJ0Y0LyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0Y9LyUpc3RyZXRjaHlHRj0vJSpzeW1tZXRyaWNHRj0vJShsYXJnZW9wR0Y9LyUubW92YWJsZWxpbWl0c0dGPS8lJ2FjY2VudEdGPS8lJ2xzcGFjZUdRLDAuMjIyMjIyMmVtRicvJSdyc3BhY2VHUSYwLjBlbUYnLUY4Ni1RIi5GJ0Y0RjtGPkZARkJGREZGRkgvRktGT0ZNLUY4Ni1RIn5GJ0Y0RjtGPkZARkJGREZGRkhGU0ZNLUklbXN1cEdGJDYlLUYxNiRRIjJGJ0Y0LUYjNiUtRjE2JFEjNjRGJ0Y0LyUrZXhlY3V0YWJsZUdGPUY0LyUxc3VwZXJzY3JpcHRzaGlmdEdGMy1GODYtUSgmbWludXM7RidGNEY7Rj5GQEZCRkRGRkZIRkovRk5GTC1GMTYkUSIxRidGNEZcb0Y0RjQvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRidGXG9GNA==

any integer LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JlEiYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEifkYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTkYyRjw=(and I mean any) can be written as LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYvLUkjbWlHRiQ2JlEiYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEifkYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTi1GOTYuUSI9RidGMkY8Rj5GQEZCRkRGRkZIRkovRk1RLDAuMjc3Nzc3OGVtRicvRlBGVUY4LUklbXN1cEdGJDYlLUkobWZlbmNlZEdGJDYlLUYjNiYtRjk2LlEqJnVtaW51czA7RidGMkY8Rj5GQEZCRkRGRkZIRkovRk1RLDAuMjIyMjIyMmVtRicvRlBGXW8tSSNtbkdGJDYlUSIxRidGMkY8RjJGPEYyRjwtRiM2JS1GLDYmUSJzRidGL0YyRjVGMkY8LyUxc3VwZXJzY3JpcHRzaGlmdEdRIjBGJ0Y4LUY5Ni5RJiZTdW07RidGMkY8Rj5GQC9GQ0YxRkQvRkdGMS9GSUYxRkpGTC9GUFEsMC4xNjY2NjY3ZW1GJy1JJW1zdWJHRiQ2JUYrLUYjNictRiw2JlEiaUYnRi9GMkY1LUknbXNwYWNlR0YkNiYvJSdoZWlnaHRHUSYwLjBleEYnLyUmd2lkdGhHRk4vJSZkZXB0aEdGYHEvJSpsaW5lYnJlYWtHUShuZXdsaW5lRidGOEYyRjwvJS9zdWJzY3JpcHRzaGlmdEdGam9GOC1GWDYlLUZgbzYlUSIyRidGMkY8LUYjNictRmBvNiVRIzY0RidGMkY8RjgtRmVuNiUtRiM2J0ZocC1GOTYuUSgmbWludXM7RidGMkY8Rj5GQEZCRkRGRkZIRkpGXG9GXm9GX29GMkY8RjJGPEYyRjxGaG9GOEYyRjw= where LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYsLUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEiYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtSSNtbkdGJDYlUSIxRidGNS9GOVEnbm9ybWFsRidGNUZBLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSIsRidGNUZBLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRkc2LlEifkYnRjVGQUZKL0ZNRjdGTkZQRlJGVEZWRlgvRmZuRlotRkc2LlEjLi5GJ0Y1RkFGSkZbb0ZORlBGUkZURlYvRllRLDAuMjIyMjIyMmVtRidGXG8tRkc2LlEiLkYnRjVGQUZKRltvRk5GUEZSRlRGVkZYRlxvRkZGaG4tRiw2JUYuLUYjNiUtRi82JlEiZEYnRjJGNUY4RjVGQUZDRjVGQQ== are the base-LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1cEdGJDYlLUkjbW5HRiQ2JFEiMkYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1GIzYlLUYvNiRRIzY0RidGMi8lJ2l0YWxpY0dRJXRydWVGJy9GM1EnaXRhbGljRicvJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnRjI= digits of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn, LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYuLUkjbW5HRiQ2JVEiMEYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLUkjbW9HRiQ2LlEifkYnRi9GMi8lJmZlbmNlR0YxLyUqc2VwYXJhdG9yR0YxLyUpc3RyZXRjaHlHRjEvJSpzeW1tZXRyaWNHRjEvJShsYXJnZW9wR0YxLyUubW92YWJsZWxpbWl0c0dGMS8lJ2FjY2VudEdGMS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRkktRjY2LlElJmxlO0YnRi9GMkY5RjtGPUY/RkFGQ0ZFL0ZIUSwwLjI3Nzc3NzhlbUYnL0ZLRlBGNS1JJW1zdWJHRiQ2JS1JI21pR0YkNiZRImFGJy8lJ2l0YWxpY0dRJXRydWVGJ0YvL0YzUSdpdGFsaWNGJy1GIzYlLUZWNiZRImlGJ0ZZRi9GZm5GL0YyLyUvc3Vic2NyaXB0c2hpZnRHRi5GNS1GNjYuUSI8RidGL0YyRjlGO0Y9Rj9GQUZDRkVGT0ZRRjUtSSVtc3VwR0YkNiUtRiw2JVEiMkYnRi9GMi1GIzYlLUYsNiVRIzY0RidGL0YyRi9GMi8lMXN1cGVyc2NyaXB0c2hpZnRHRi4tRjY2LlEiLkYnRi9GMkY5RjtGPUY/RkFGQ0ZFRkdGSkYvRjI=

For example

a:=7^1234-1;

A:=convert(a,base,2^64);

b:=add(A[i]*2^(64*(i-1)),i=1..nops(A));

a-b;

jjj

The de-facto standard for integer arithmetic is GMP (GNU Multi-Precision). This is an open-source C library (with assembly language kernels) which is used by most computer algebra and computational number theory systems.

See http://gmplib.org/

<Text-field bookmark="Asymptotic Notation" style="Heading 1" layout="Heading 1">Asymptotic notation</Text-field>

We will use big-Oh (O(..)), big-Omega ( \316\251(...) ) and big-Theta ( \316\230(...) ).

Be familiar with it...

<Text-field bookmark="Multiprecision Addition" style="Heading 1" layout="Heading 1">Addition of multiprecision numbers (radix B)</Text-field>

Input:

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzZkby1JJW1zdWJHRiQ2JS1JI21pR0YkNiVRImFGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictRiM2JS1JI21uR0YkNiRRIjBGJy9GNlEnbm9ybWFsRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJ0Y+LyUvc3Vic2NyaXB0c2hpZnRHRj0tSSNtb0dGJDYtUSIrRidGPi8lJmZlbmNlR0ZCLyUqc2VwYXJhdG9yR0ZCLyUpc3RyZXRjaHlHRkIvJSpzeW1tZXRyaWNHRkIvJShsYXJnZW9wR0ZCLyUubW92YWJsZWxpbWl0c0dGQi8lJ2FjY2VudEdGQi8lJ2xzcGFjZUdRLDAuMjIyMjIyMmVtRicvJSdyc3BhY2VHRlktRiw2JUYuLUYjNiUtRjs2JFEiMUYnRj5GQEY+RkMtRi82JVEiQkYnRjJGNS1GRjYtUSJ+RidGPkZJRktGTUZPRlFGU0ZVL0ZYUSYwLjBlbUYnL0ZlbkZkb0ZFRmBvLUYsNiVGLi1GIzYlLUY7NiRRIjJGJ0Y+RkBGPkZDLUklbXN1cEdGJDYlRl1vRmhvLyUxc3VwZXJzY3JpcHRzaGlmdEdGPUZFLUZGNi1RIy4uRidGPkZJRktGTUZPRlFGU0ZVRldGZW8tRkY2LVEiLkYnRj5GSUZLRk1GT0ZRRlNGVUZjb0Zlb0ZFLUYsNiVGLi1GIzYlLUYvNiVRIm1GJ0YyRjVGQEY+RkMtRl5wNiVGXW8tRiM2KUZccS1JJ21zcGFjZUdGJDYmLyUnaGVpZ2h0R1EmMC4wZXhGJy8lJndpZHRoR0Zkby8lJmRlcHRoR0ZocS8lKmxpbmVicmVha0dRKG5ld2xpbmVGJ0ZjcS1GZHE2JkZmcUZpcUZbci9GXnJRJWF1dG9GJ0Zgb0ZARj5GYHAtRi82I1EhRidGY3FGYG9GYG9GYG9GYG9GYG9GYG9GRS1GLDYlLUYvNiVRImJGJ0YyRjVGOEZDRmBvRkUtRiw2JUZpckZobkZDRl1vRmBvRkUtRiw2JUZpckZob0ZDRl1wRkVGYnBGZXBGRS1GLDYlRmlyRmpwRkMtRl5wNiVGXW9GanBGYHBGZHJGY3FGYG9GYG9GYG9GYG9GYG9GYG8tRkY2LVEiPUYnRj5GSUZLRk1GT0ZRRlNGVS9GWFEsMC4yNzc3Nzc4ZW1GJy9GZW5GaHNGYG8tSShtZmVuY2VkR0YkNiQtRiM2KUYrRmBvRkVGYG9GZ3JGQEY+Rj5GYG9GRUZgby1GW3Q2JC1GIzYpRmZuRmBvRkVGYG9GXHNGQEY+Rj5GYG9GXW9GYG9GRUZgby1GW3Q2JC1GIzYpRmZvRmBvRkVGYG9GXnNGQEY+Rj5GXXBGYG9GRUZgb0ZicEZlcEZgb0ZFLUZbdDYkLUYjNidGaHBGRUZgc0ZARj5GPkZic0ZARj4=

Note that LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYzLUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEiYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtSSNtbkdGJDYlUSIwRidGNS9GOVEnbm9ybWFsRidGNUZBLyUvc3Vic2NyaXB0c2hpZnRHRkAtSSNtb0dGJDYuUSJ+RidGNUZBLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjcvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGWS1GRjYuUSIrRidGNUZBRklGS0ZNRk9GUUZTRlUvRlhRLDAuMjIyMjIyMmVtRicvRmVuRmpuRkUtRiw2JS1GLzYmUSJiRidGMkY1RjhGO0ZDRkUtRkY2LlEiPUYnRjVGQUZJRktGTUZPRlFGU0ZVL0ZYUSwwLjI3Nzc3NzhlbUYnL0ZlbkZlb0ZFLUYsNiUtRi82JlEiY0YnRjJGNUY4RjtGQ0ZFRmZuRkUtRiw2JS1GLzYmUScmIzk0NztGJy9GM0Y3RjVGQUY7RkNGRS1GLzYmUSJCRidGMkY1RjhGNUZB (where LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEnJiM5NDc7RicvJSdpdGFsaWNHUSZmYWxzZUYnLyUrZXhlY3V0YWJsZUdGNC8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRictRiM2JS1GLzYmUSJpRicvRjNRJXRydWVGJ0Y1L0Y4USdpdGFsaWNGJ0Y1RjcvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJy1JI21vR0YkNi5RKiZFbGVtZW50O0YnRjVGNy8lJmZlbmNlR0Y0LyUqc2VwYXJhdG9yR0Y0LyUpc3RyZXRjaHlHRjQvJSpzeW1tZXRyaWNHRjQvJShsYXJnZW9wR0Y0LyUubW92YWJsZWxpbWl0c0dGNC8lJ2FjY2VudEdGNC8lJ2xzcGFjZUdRLDAuMjc3Nzc3OGVtRicvJSdyc3BhY2VHRlotRkc2LlEifkYnRjVGN0ZKRkxGTkZQRlJGVEZWL0ZZUSYwLjBlbUYnL0ZmbkZbby1JKG1mZW5jZWRHRiQ2Jy1GIzYnLUkjbW5HRiQ2JUZFRjVGNy1GRzYuUSIsRidGNUY3RkovRk1GQEZORlBGUkZURlZGam4vRmZuUSwwLjMzMzMzMzNlbUYnLUZjbzYlUSIxRidGNUY3RjVGN0Y1RjcvJSVvcGVuR1EifGZyRicvJSZjbG9zZUdRInxockYnRjVGNw==).

Furthermore LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY1LUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEiYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtSSNtbkdGJDYlUSIxRidGNS9GOVEnbm9ybWFsRidGNUZBLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSJ+RidGNUZBLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjcvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGWi1GRzYuUSIrRidGNUZBRkpGTEZORlBGUkZURlYvRllRLDAuMjIyMjIyMmVtRicvRmZuRltvRkYtRiw2JS1GLzYmUSJiRidGMkY1RjhGO0ZDRmduLUYsNiUtRi82JlEnJiM5NDc7RicvRjNGN0Y1RkEtRiM2JS1GPjYlRkVGNUZBRjVGQUZDRkYtRkc2LlEiPUYnRjVGQUZKRkxGTkZQRlJGVEZWL0ZZUSwwLjI3Nzc3NzhlbUYnL0ZmbkZgcEZGLUYsNiUtRi82JlEiY0YnRjJGNUY4RjtGQ0ZGRmduRkYtRiw2JUZkb0Y7RkNGRi1GLzYmUSJCRidGMkY1RjhGNUZB (where JSFHLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEnJiM5NDc7RicvJSdpdGFsaWNHUSZmYWxzZUYnLyUrZXhlY3V0YWJsZUdGNC8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRictRiM2JS1JI21uR0YkNiVRIjFGJ0Y1RjdGNUY3LyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSomRWxlbWVudDtGJ0Y1RjcvJSZmZW5jZUdGNC8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSwwLjI3Nzc3NzhlbUYnLyUncnNwYWNlR0ZXLUZENi5RIn5GJ0Y1RjdGR0ZJRktGTUZPRlFGUy9GVlEmMC4wZW1GJy9GWUZobi1JKG1mZW5jZWRHRiQ2Jy1GIzYnLUY9NiVGQkY1RjctRkQ2LlEiLEYnRjVGN0ZHL0ZKUSV0cnVlRidGS0ZNRk9GUUZTRmduL0ZZUSwwLjMzMzMzMzNlbUYnRjxGNUY3RjVGNy8lJW9wZW5HUSJ8ZnJGJy8lJmNsb3NlR1EifGhyRidGNUY3).

So the carry is either 0 or 1.

Cost of adding two integers of length LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn is bounded by the cost of adding m digits together (plus the carries). Assuming the digits are of constant size (which is reasonable), the cost is O(m).

<Text-field bookmark="Polynomial Representation" style="Heading 1" layout="Heading 1">Representation and addition of polynomials</Text-field>

Polynomials have many similar properties to integers, but also many differences.

f:=3*x^5+12*x+2;

g:=2*x^6+4*x;

f+g;

sort(%);

Coefficients 3, 12, 2, etc. come from the ring of integers

(in this course a ring is always a commutative ring with identity).

We will see other rings later (e.g. integers modulo a composite number N)

A polynomial

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEifkYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTi1GOTYuUSomRWxlbWVudDtGJ0YyRjxGPkZARkJGREZGRkhGSi9GTVEsMC4yNzc3Nzc4ZW1GJy9GUEZVLUYsNiZRIlJGJ0YvRjJGNS1JKG1mZW5jZWRHRiQ2Jy1GIzYlLUYsNiZRInhGJ0YvRjJGNUYyRjxGMkY8LyUlb3BlbkdRIltGJy8lJmNsb3NlR1EiXUYnRjJGPA==, over a ring LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn, is a finite sequence LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYvLUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtSSNtbkdGJDYlUSIwRidGNS9GOVEnbm9ybWFsRidGNUZBLyUvc3Vic2NyaXB0c2hpZnRHRkAtSSNtb0dGJDYuUSIsRidGNUZBLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRkY2LlEifkYnRjVGQUZJL0ZMRjdGTUZPRlFGU0ZVRlcvRmVuRlktRiw2JUYuLUYjNiUtRj42JVEiMUYnRjVGQUY1RkFGQ0ZFRmduLUZGNi5RIy4uRidGNUZBRklGam5GTUZPRlFGU0ZVL0ZYUSwwLjIyMjIyMjJlbUYnRltvLUZGNi5RIi5GJ0Y1RkFGSUZqbkZNRk9GUUZTRlVGV0Zbb0ZFRmduLUYsNiVGLi1GIzYlLUYvNiZRIm5GJ0YyRjVGOEY1RkFGQ0Y1RkE= such that

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYxLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUwZm9udF9zdHlsZV9uYW1lR1EoMkR+TWF0aEYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi5RIj1GJ0YyL0Y2USdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGQC8lKXN0cmV0Y2h5R0ZALyUqc3ltbWV0cmljR0ZALyUobGFyZ2VvcEdGQC8lLm1vdmFibGVsaW1pdHNHRkAvJSdhY2NlbnRHRkAvJSdsc3BhY2VHUSwwLjI3Nzc3NzhlbUYnLyUncnNwYWNlR0ZPLUklbXN1YkdGJDYlRistRiM2JS1JI21uR0YkNiVRIjBGJ0YyRjwvJStleGVjdXRhYmxlR0ZARjwvJS9zdWJzY3JpcHRzaGlmdEdGWi1GOTYuUSIrRidGMkY8Rj5GQUZDRkVGR0ZJRksvRk5RLDAuMjIyMjIyMmVtRicvRlFGXW8tRlM2JUYrLUYjNiUtRlg2JVEiMUYnRjJGPEZlbkY8RmduLUYsNiZRInhGJ0YvRjJGNUZpbi1GOTYuUSMuLkYnRjJGPEY+RkFGQ0ZFRkdGSUZLRlxvL0ZRUSYwLjBlbUYnLUY5Ni5RIi5GJ0YyRjxGPkZBRkNGRUZHRklGSy9GTkZdcEZccEZpbi1GUzYlRistRiM2JS1GLDYmUSJuRidGL0YyRjVGZW5GPEZnbi1JJW1zdXBHRiQ2JUZmb0ZkcC8lMXN1cGVyc2NyaXB0c2hpZnRHRlotRiw2I1EhRidGZW5GPA==

If LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlErJk5vdEVxdWFsO0YnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTi1JI21uR0YkNiVRIjBGJ0YyRjxGMkY8 the we assume that LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtRi82JlEibkYnRjJGNUY4RjUvRjlRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSsmTm90RXF1YWw7RidGNUZALyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjcvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGWS1JI21uR0YkNiVGREY1RkBGNUZA and the degree of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn is

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JVEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIi5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTC8lK2V4ZWN1dGFibGVHRj1GOQ==

<Text-field style="Heading 3" layout="Heading 3">Dense representation</Text-field>

The dense representation of a polynomial is simply a list or array of all its coefficients, in order

For example LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYyLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiPUYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTi1JJW1zdWJHRiQ2JUYrLUYjNiYtSSNtbkdGJDYlUSIwRidGMkY8RjIvJTBmb250X3N0eWxlX25hbWVHUSkyRH5JbnB1dEYnRjwvJS9zdWJzY3JpcHRzaGlmdEdGWS1GOTYuUSIrRidGMkY8Rj5GQEZCRkRGRkZIRkovRk1RLDAuMjIyMjIyMmVtRicvRlBGXW8tRlI2JUYrLUYjNiYtRlc2JVEiMUYnRjJGPEYyRlpGPEZnbi1GLDYmUSJ4RidGL0YyRjVGaW4tRjk2LlEjLi5GJ0YyRjxGPkZARkJGREZGRkhGSkZcby9GUFEmMC4wZW1GJy1GOTYuUSIuRidGMkY8Rj5GQEZCRkRGRkZIRkovRk1GXXBGXHBGaW4tRlI2JUYrLUYjNiYtRiw2JlEibkYnRi9GMkY1RjJGWkY8RmduLUklbXN1cEdGJDYlRmZvRmRwLyUxc3VwZXJzY3JpcHRzaGlmdEdGWS1GLDYjUSFGJ0YyRlpGPA== is represented as LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkobWZlbmNlZEdGJDYnLUYjNjMtSSVtc3ViR0YkNiUtSSNtaUdGJDYmUSJmRicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictRiM2Ji1JI21uR0YkNiVRIjBGJ0Y6L0Y+USdub3JtYWxGJ0Y6LyUwZm9udF9zdHlsZV9uYW1lR1EpMkR+SW5wdXRGJ0ZGLyUvc3Vic2NyaXB0c2hpZnRHRkUtSSNtb0dGJDYuUSIsRidGOkZGLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRk42LlEifkYnRjpGRkZRL0ZURjxGVUZXRllGZW5GZ25GaW4vRl1vRltvLUYxNiVGMy1GIzYmLUZDNiVRIjFGJ0Y6RkZGOkZIRkZGS0ZNRl9vLUYxNiVGMy1GIzYmLUZDNiVRIjJGJ0Y6RkZGN0Y6Rj1GS0ZNRl9vLUZONi5RIy4uRidGOkZGRlFGYm9GVUZXRllGZW5GZ24vRmpuUSwwLjIyMjIyMjJlbUYnRmNvLUZONi5RIi5GJ0Y6RkZGUUZib0ZVRldGWUZlbkZnbkZpbkZjb0ZNRl9vLUYxNiVGMy1GIzYmLUY0NiZRIm5GJ0Y3RjpGPUY6RkhGRkZLRjpGSEZGRjpGRi8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJy1GNDYjUSFGJ0Y6RkhGRg==, an array of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiK0YnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yMjIyMjIyZW1GJy8lJ3JzcGFjZUdGTi1JI21uR0YkNiVRIjFGJ0YyRjxGMkY8 elements of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn.JSFH

PolynomialTools[CoefficientVector](f,x);

This uses the function (CoefficientVector) in the PolynomialTools package

<Text-field style="Heading 3" layout="Heading 3">Sparse representation</Text-field>

The sparse representation of a polynomial is a list of coefficient/exponent pairs

So LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkrbXVuZGVyb3ZlckdGJDYnLUkjbW9HRiQ2LVEmJlN1bTtGJy8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRicvJSZmZW5jZUdRJnVuc2V0RicvJSpzZXBhcmF0b3JHRjcvJSlzdHJldGNoeUdRJXRydWVGJy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMTY2NjY2N2VtRictRiM2Ji1JI21pR0YkNiVRImlGJy8lJ2l0YWxpY0dGPC9GM1EnaXRhbGljRictRi82LVEiPUYnRjIvRjZRJmZhbHNlRicvRjlGWS9GO0ZZL0Y+RlkvRkBGWS9GQkZZL0ZERlkvRkZRLDAuMjc3Nzc3OGVtRicvRklGW28tSSNtbkdGJDYkUSIxRidGMkYyLUYjNiUtRk42JVEidEYnRlFGU0ZRRlNGaW4vJSxhY2NlbnR1bmRlckdGWS1JJW1zdWJHRiQ2JS1GTjYlUSJhRidGUUZTLUYjNiVGTUZRRlMvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJy1JJW1zdXBHRiQ2JS1GTjYlUSJ4RidGUUZTLUYjNiUtRmlvNiUtRk42JVEiZUYnRlFGU0ZecEZgcEZRRlMvJTFzdXBlcnNjcmlwdHNoaWZ0R0ZicC1GTjYjUSFGJ0Yy would be represented as

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYxLUkobWZlbmNlZEdGJDYmLUYjNigtSSVtc3ViR0YkNiUtSSNtaUdGJDYmUSJhRicvJSdpdGFsaWNHUSV0cnVlRicvJTBmb250X3N0eWxlX25hbWVHUSgyRH5NYXRoRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNictSSNtbkdGJDYmUSIxRidGN0Y6Rj1GNy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnRjpGPS8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYnLUkjbW9HRiQ2L1EiLEYnRjdGOkY9LyUmZmVuY2VHRkgvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGSC8lKnN5bW1ldHJpY0dGSC8lKGxhcmdlb3BHRkgvJS5tb3ZhYmxlbGltaXRzR0ZILyUnYWNjZW50R0ZILyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2JS1GNDYmUSJlRidGN0Y6Rj1GQEZJRjdGRkY9RjdGOkY9RkwtRk02L1EifkYnRjdGOkY9RlAvRlNGSEZURlZGWEZaRmZuRmhuL0Zcb0Zqbi1GLDYmLUYjNigtRjE2JUYzLUYjNictRkM2JlEiMkYnRjdGOkY9RjdGRkY6Rj1GSUZMLUYxNiVGYG9GXnBGSUY3RkZGPUY3RjpGPUZMRmNvLUZNNi9RIy4uRidGN0Y6Rj1GUEZmb0ZURlZGWEZaRmZuL0ZpblEsMC4yMjIyMjIyZW1GJ0Znby1GTTYvUSIuRidGN0Y6Rj1GUEZmb0ZURlZGWEZaRmZuRmhuRmdvRkxGY28tRiw2Ji1GIzYoLUYxNiVGMy1GIzYnLUY0NiZRInRGJ0Y3RjpGPUY3RkZGOkY9RklGTC1GMTYlRmBvRmNxRklGN0ZGRj1GN0Y6Rj0tRjQ2I1EhRidGN0ZGRj0=

C:=[coeffs(f,x,'V')];

seq([C[i],degree(V[i])],i=1..nops(C));

<Text-field style="Heading 3" layout="Heading 3">Addition</Text-field>

In symbolic computation we often use other representations, some of which we will see here

Black box representation \342\200\223 representing symbolic objects as functions which produce values

Straight-line programs or algebraic circuits \342\200\223 representing symbolic objects as programs (which produce values and can be manipulated as programs)JSFH

Addition of two polynomials with degree bounded by LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn costs at most LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiK0YnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yMjIyMjIyZW1GJy8lJ3JzcGFjZUdGTi1JI21uR0YkNiVRIjFGJ0YyRjxGMkY8 additions in LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn.

We will usually analyze algorithms over a ring LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn in terms of the number of operations from LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn.

I.e., we will write LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JlEiT0YnLyUnaXRhbGljR1EmZmFsc2VGJy8lK2V4ZWN1dGFibGVHRjEvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLUkobWZlbmNlZEdGJDYlLUYjNiUtRiw2JlEibkYnL0YwUSV0cnVlRidGMi9GNVEnaXRhbGljRidGMkY0RjJGNEYyRjQ= operations in LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn.

What is the cost in word operations if LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiPUYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTi1GLDYmUSgmIzg0ODQ7RidGL0YyRjVGMkY8 ?

In this case we count machine operations and must take into account the size of the coefficients in \342\204\244.

Assume that the absolute values of all coefficients of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn are bounded by B (i.e., LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkobWZlbmNlZEdGJDYnLUYjNiUtSSVtc3ViR0YkNiUtSSNtaUdGJDYmUSJmRicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictRiM2JS1GNDYmUSJpRidGN0Y6Rj1GOi9GPlEnbm9ybWFsRicvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJ0Y6RkVGOkZFLyUlb3BlbkdRInxnckYnLyUmY2xvc2VHRkwtSSNtb0dGJDYuUSJ+RidGOkZFLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjwvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGXW8tRlA2LlElJmxlO0YnRjpGRUZTRlVGV0ZZRmVuRmduRmluL0Zcb1EsMC4yNzc3Nzc4ZW1GJy9GX29GZG8tRjQ2JlEiQkYnRjdGOkY9RjpGRQ== )

Additions with integers of absolute value LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbW9HRiQ2LlElJmxlO0YnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGMS8lKGxhcmdlb3BHRjEvJS5tb3ZhYmxlbGltaXRzR0YxLyUnYWNjZW50R0YxLyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGRS1JI21pR0YkNiZRIkJGJy8lJ2l0YWxpY0dRJXRydWVGJ0YvL0YzUSdpdGFsaWNGJ0YvRjI= take LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JlEiT0YnLyUnaXRhbGljR1EmZmFsc2VGJy8lK2V4ZWN1dGFibGVHRjEvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLUkobWZlbmNlZEdGJDYlLUYjNiYtRiw2JlEkbG9nRidGL0YyRjQtRjg2JS1GIzYlLUYsNiZRIkJGJy9GMFEldHJ1ZUYnRjIvRjVRJ2l0YWxpY0YnRjJGNEYyRjRGMkY0RjJGNEYyRjQ= operations.

Cost two add two polynomials of degree LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbW9HRiQ2LlElJmxlO0YnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGMS8lKGxhcmdlb3BHRjEvJS5tb3ZhYmxlbGltaXRzR0YxLyUnYWNjZW50R0YxLyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGRS1JI21pR0YkNiZRIm5GJy8lJ2l0YWxpY0dRJXRydWVGJ0YvL0YzUSdpdGFsaWNGJ0YvRjI= with coefficients of absolute value LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbW9HRiQ2LlElJmxlO0YnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGMS8lKGxhcmdlb3BHRjEvJS5tb3ZhYmxlbGltaXRzR0YxLyUnYWNjZW50R0YxLyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGRS1JI21pR0YkNiZRIkJGJy8lJ2l0YWxpY0dRJXRydWVGJ0YvL0YzUSdpdGFsaWNGJ0YvRjI= is LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEiT0YnLyUnaXRhbGljR1EmZmFsc2VGJy8lK2V4ZWN1dGFibGVHRjEvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLUkobWZlbmNlZEdGJDYlLUYjNigtRiw2JlEibkYnL0YwUSV0cnVlRidGMi9GNVEnaXRhbGljRictSSNtb0dGJDYuUSJ+RidGMkY0LyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGMS8lKGxhcmdlb3BHRjEvJS5tb3ZhYmxlbGltaXRzR0YxLyUnYWNjZW50R0YxLyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGVy1GLDYmUSRsb2dGJ0YvRjJGNC1GODYlLUYjNiUtRiw2JlEiQkYnRj9GMkZBRjJGNEYyRjRGMkY0RjJGNC1GLDYjUSFGJ0YyRjQ= word operations.

Note: similarities and differences between \342\204\244 and R[x].

no carries to worry about in R[x]

many algorithms for R[x] carry over to \342\204\244.

not all techniques in R[x] work in \342\204\244.

<Text-field style="Heading 3" layout="Heading 3">Polynomial Reversion</Text-field>

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzZLLUkjbWlHRiQ2JVEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj1GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JJW1zdWJHRiQ2JUYrLUYjNiUtSSNtbkdGJDYkUSIwRidGOS8lK2V4ZWN1dGFibGVHRj1GOS8lL3N1YnNjcmlwdHNoaWZ0R0ZXLUY2Ni1RIitGJ0Y5RjtGPkZARkJGREZGRkgvRktRLDAuMjIyMjIyMmVtRicvRk5Gam4tRlA2JUYrLUYjNiUtRlU2JFEiMUYnRjlGWEY5RlotRiw2JVEieEYnRi9GMkZmbi1GNjYtUSMuLkYnRjlGO0Y+RkBGQkZERkZGSEZpbi9GTlEmMC4wZW1GJy1GNjYtUSIuRidGOUY7Rj5GQEZCRkRGRkZIL0ZLRmpvRmlvRmZuLUZQNiVGKy1GIzYlLUYsNiVRIm5GJ0YvRjJGWEY5RlotSSVtc3VwR0YkNiVGY29GYXAvJTFzdXBlcnNjcmlwdHNoaWZ0R0ZXLUY2Ni1RIn5GJ0Y5RjtGPkZARkJGREZGRkhGXnBGaW9GW3FGW3EtRjY2L1EzJkRvdWJsZVJpZ2h0QXJyb3c7RicvJSVib2xkR0YxL0YzUSVib2xkRicvJStmb250d2VpZ2h0R0ZkcUY7Rj4vRkFGMUZCRkRGRkZIRkpGTS1GNjYvRl1xRmFxRmNxRmVxRjtGPkZARkJGREZGRkhGXnBGaW8tRiw2JVEpcmV2ZXJzYWxGJ0YvRjItSShtZmVuY2VkR0YkNiQtRiM2JUYrRlhGOUY5RjVGW3FGX3BGZm4tRlA2JUYrLUYjNidGY3AtRjY2LVEoJm1pbnVzO0YnRjlGO0Y+RkBGQkZERkZGSEZpbkZbb0Zgb0ZYRjlGWkZjb0ZmbkZmb0ZbcEZmbkZPRmZwRltxRjVGW3FGKy1GXnI2JC1GIzYlLUkmbWZyYWNHRiQ2KEZgby1GIzYlRmNvRlhGOS8lLmxpbmV0aGlja25lc3NHRmJvLyUrZGVub21hbGlnbkdRJ2NlbnRlckYnLyUpbnVtYWxpZ25HRmZzLyUpYmV2ZWxsZWRHRj1GWEY5RjktRjY2LVEnJnNkb3Q7RidGOUY7Rj5GQEZCRkRGRkZIRl5wRmlvRmZwRltxRlhGOQ==

Note that LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2JlEpcmV2ZXJzYWxGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2JS1GIzYmRistRjk2JS1GIzYlLUYsNiZRImZGJ0YvRjJGNUYyL0Y2USdub3JtYWxGJ0YyRkRGMkZERjJGRC1JI21vR0YkNi5RIj1GJ0YyRkQvJSZmZW5jZUdGNC8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSwwLjI3Nzc3NzhlbUYnLyUncnNwYWNlR0ZaRkFGMkZE. No analogue for integers.

This operation turns out to be very useful.

eval(f,x=3);

frev:=expand(x^degree(f,x)*eval(f,x=1/x));

<Text-field bookmark="Polynomial Multiplication" style="Heading 1" layout="Heading 1">Polynomial Multiplication</Text-field>

First consider polynomials in

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JVEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYlLUYsNiVRInhGJ0YvRjIvJStleGVjdXRhYmxlR1EmZmFsc2VGJy9GM1Enbm9ybWFsRidGQC8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJy1JI21vR0YkNi1RIi5GJ0ZALyUmZmVuY2VHRj8vJSpzZXBhcmF0b3JHRj8vJSlzdHJldGNoeUdGPy8lKnN5bW1ldHJpY0dGPy8lKGxhcmdlb3BHRj8vJS5tb3ZhYmxlbGltaXRzR0Y/LyUnYWNjZW50R0Y/LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGZm5GPUZA

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY7LUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEifkYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTi1GOTYuUSI9RidGMkY8Rj5GQEZCRkRGRkZIRkovRk1RLDAuMjc3Nzc3OGVtRicvRlBGVUY4LUklbXN1YkdGJDYlRistRiM2JS1JI21uR0YkNiVRIjBGJ0YyRjxGMkY8LyUvc3Vic2NyaXB0c2hpZnRHRmluLUY5Ni5RIitGJ0YyRjxGPkZARkJGREZGRkhGSi9GTVEsMC4yMjIyMjIyZW1GJy9GUEZgby1GWDYlRistRiM2JS1GZ242JVEiMUYnRjJGPEYyRjxGam4tRiw2JlEieEYnRi9GMkY1RjhGXG9GOC1GWDYlRistRiM2JS1GZ242JVEiMkYnRjJGPEYyRjxGam4tSSVtc3VwR0YkNiVGaW9GXnAvJTFzdXBlcnNjcmlwdHNoaWZ0R0ZpbkZcb0Y4LUY5Ni5RIy4uRidGMkY8Rj5GQEZCRkRGRkZIRkpGX29GTy1GOTYuUSIuRidGMkY8Rj5GQEZCRkRGRkZIRkpGTEZPRjhGXG9GOC1GWDYlRistRiM2JS1GLDYmUSJuRidGL0YyRjVGMkY8RmpuLUZkcDYlRmlvRmBxRmZwRjhGMkY8 and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY8LUkjbWlHRiQ2JlEiZ0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEifkYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTi1GOTYuUSI9RidGMkY8Rj5GQEZCRkRGRkZIRkovRk1RLDAuMjc3Nzc3OGVtRicvRlBGVUY4LUklbXN1YkdGJDYlRistRiM2JS1JI21uR0YkNiVRIjBGJ0YyRjxGMkY8LyUvc3Vic2NyaXB0c2hpZnRHRmluLUY5Ni5RIitGJ0YyRjxGPkZARkJGREZGRkhGSi9GTVEsMC4yMjIyMjIyZW1GJy9GUEZgb0Y4LUZYNiVGKy1GIzYlLUZnbjYlUSIxRidGMkY8RjJGPEZqbi1GLDYmUSJ4RidGL0YyRjVGOEZcb0Y4LUZYNiVGKy1GIzYlLUZnbjYlUSIyRidGMkY8RjJGPEZqbkY4LUklbXN1cEdGJDYlRmlvRl5wLyUxc3VwZXJzY3JpcHRzaGlmdEdGaW5GXG9GOC1GOTYuUSMuLkYnRjJGPEY+RkBGQkZERkZGSEZKRl9vRk8tRjk2LlEiLkYnRjJGPEY+RkBGQkZERkZGSEZKRkxGT0Y4RlxvRjgtRlg2JUYrLUYjNiUtRiw2JlEibUYnRi9GMkY1RjJGPEZqbi1GZHA2JUZpb0ZgcUZmcEYyRjw=

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

The LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzZCLUkjbW9HRiQ2LlEifkYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGMS8lKGxhcmdlb3BHRjEvJS5tb3ZhYmxlbGltaXRzR0YxLyUnYWNjZW50R0YxLyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGRS1JI21pR0YkNiZRImZGJy8lJ2l0YWxpY0dRJXRydWVGJ0YvL0YzUSdpdGFsaWNGJ0YrLUYsNi5RJyZzZG90O0YnRi9GMkY1RjdGOUY7Rj1GP0ZBRkNGRi1GSTYmUSJnRidGTEYvRk9GKy1GLDYuUSI9RidGL0YyRjVGN0Y5RjtGPUY/RkEvRkRRLDAuMjc3Nzc3OGVtRicvRkdGZW5GKy1JJW1zdWJHRiQ2JS1GSTYmUSJoRidGTEYvRk8tRiM2JS1JI21uR0YkNiVRIjBGJ0YvRjJGL0YyLyUvc3Vic2NyaXB0c2hpZnRHRmJvLUYsNi5RIitGJ0YvRjJGNUY3RjlGO0Y9Rj9GQS9GRFEsMC4yMjIyMjIyZW1GJy9GR0Zpb0YrLUZobjYlRmpuLUYjNiUtRmBvNiVRIjFGJ0YvRjJGL0YyRmNvLUZJNiZRInhGJ0ZMRi9GT0YrRmVvRistRmhuNiVGam4tRiM2JS1GYG82JVEiMkYnRi9GMkYvRjJGY28tSSVtc3VwR0YkNiVGYnBGZ3AvJTFzdXBlcnNjcmlwdHNoaWZ0R0Zib0YrRmVvRistRiw2LlEjLi5GJ0YvRjJGNUY3RjlGO0Y9Rj9GQUZob0ZGLUYsNi5RIi5GJ0YvRjJGNUY3RjlGO0Y9Rj9GQUZDRkZGK0Zlb0YrLUZobjYlRmpuLUYjNictRkk2JlEibkYnRkxGL0ZPRmVvLUZJNiZRIm1GJ0ZMRi9GT0YvRjJGY28tRl1xNiVGYnBGaXFGX3FGK0YrRi9GMg== where LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYuLUklbXN1YkdGJDYlLUkjbWlHRiQ2JlEiaEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtRi82JlEia0YnRjJGNUY4RjUvRjlRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSJ+RidGNUZALyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjcvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGWS1GRjYuUSI9RidGNUZARklGS0ZNRk9GUUZTRlUvRlhRLDAuMjc3Nzc3OGVtRicvRmVuRmpuRkUtRiw2JS1GRjYuUSYmU3VtO0YnRjVGQEZJRksvRk5GNEZPL0ZSRjQvRlRGNEZVRlcvRmVuUSwwLjE2NjY2NjdlbUYnLUYjNiktRi82JlEiaUYnRjJGNUY4LUZGNi5RIitGJ0Y1RkBGSUZLRk1GT0ZRRlNGVS9GWFEsMC4yMjIyMjIyZW1GJy9GZW5GX3AtRi82JlEiakYnRjJGNUY4RmZuRj1GNUZARkItRiw2JS1GLzYmUSJmRidGMkY1RjgtRiM2JUZob0Y1RkBGQkZFLUZGNi5RJyZzZG90O0YnRjVGQEZJRktGTUZPRlFGU0ZVRldGWkZFLUYsNiUtRi82JlEiZ0YnRjJGNUY4LUYjNiVGYXBGNUZARkJGNUZA

The cost is LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkobWZlbmNlZEdGJDYlLUYjNictSSNtaUdGJDYmUSJuRicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYuUSIrRidGNy9GO1Enbm9ybWFsRicvJSZmZW5jZUdGOS8lKnNlcGFyYXRvckdGOS8lKXN0cmV0Y2h5R0Y5LyUqc3ltbWV0cmljR0Y5LyUobGFyZ2VvcEdGOS8lLm1vdmFibGVsaW1pdHNHRjkvJSdhY2NlbnRHRjkvJSdsc3BhY2VHUSwwLjIyMjIyMjJlbUYnLyUncnNwYWNlR0ZTLUkjbW5HRiQ2JVEiMUYnRjdGQUY3RkFGN0ZBLUYsNiUtRiM2Jy1GMTYmUSJtRidGNEY3RjpGPUZWRjdGQUY3RkFGN0ZB multiplications and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEnJnNkb3Q7RidGMi9GNlEnbm9ybWFsRicvJSZmZW5jZUdGNC8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZOLUYsNiZRIm1GJ0YvRjJGNUYyRjw= additions (exactly).

\316\230(nm) operations in LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn.

Integers are similar to above.

We can multiply LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEiYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEnJnNkb3Q7RidGMi9GNlEnbm9ybWFsRicvJSZmZW5jZUdGNC8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZOLUYsNiZRImJGJ0YvRjJGNUYyRjw= with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JlEiT0YnLyUnaXRhbGljR1EmZmFsc2VGJy8lK2V4ZWN1dGFibGVHRjEvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLUkobWZlbmNlZEdGJDYlLUYjNigtRiw2JlEkbG9nRidGL0YyRjQtRjg2JS1GIzYlLUYsNiZRImFGJy9GMFEldHJ1ZUYnRjIvRjVRJ2l0YWxpY0YnRjJGNEYyRjRGPC1GODYlLUYjNiUtRiw2JlEiYkYnRkZGMkZIRjJGNEYyRjRGMkY0RjJGNEYyRjQ= machine operations.

Often we will call these bit operations - the difference between a 32-bit word or a 64-bit word (or even a 1-bit word) only matters "up to a constant" (which is hidden in the big-Oh).

Of course, these constants matter a lot in practice!

f:=randpoly(x,degree=20);

g:=randpoly(x,degree=30);

h:=f*g;

h:=expand(h);

Note the use of expand. Why do we need this?

(x-1)^1000;

w:=expand((x-1)^1000):

coeff(w,x,500);

Multivariate polynomials

Polynomials often have many variables

Mathematically we write

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JVEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYnLUYsNiNRIUYnLUYjNistSSVtc3ViR0YkNiUtRiw2JVEieEYnRi9GMi1GIzYkLUkjbW5HRiQ2JFEiMUYnL0YzUSdub3JtYWxGJ0ZLLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYtUSIsRidGSy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGMS8lKXN0cmV0Y2h5R0ZWLyUqc3ltbWV0cmljR0ZWLyUobGFyZ2VvcEdGVi8lLm1vdmFibGVsaW1pdHNHRlYvJSdhY2NlbnRHRlYvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR1EsMC4zMzMzMzMzZW1GJy1GQDYlRkItRiM2JC1GSDYkUSIyRidGS0ZLRk1GUC1GUTYtUSMuLkYnRktGVC9GWEZWRllGZW5GZ25GaW5GW28vRl5vUSwwLjIyMjIyMjJlbUYnL0Zhb0Zfby1GUTYtUSIuRidGS0ZURl1wRllGZW5GZ25GaW5GW29GXW9GYHBGUC1GQDYlRkItRiM2JC1GLDYlUSJtRidGL0YyRktGTUZLRjovJStleGVjdXRhYmxlR0ZWRktGSy8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJ0Y6RltxRks= for the ring of polynomials in variables LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYrLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEieEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUkjbW5HRiQ2JFEiMUYnL0Y2USdub3JtYWxGJ0Y+LyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYtUSIsRidGPi8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0ZJLyUqc3ltbWV0cmljR0ZJLyUobGFyZ2VvcEdGSS8lLm1vdmFibGVsaW1pdHNHRkkvJSdhY2NlbnRHRkkvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR1EsMC4zMzMzMzMzZW1GJy1GLDYlRi4tRiM2JC1GOzYkUSIyRidGPkY+RkBGQy1GRDYtUSMuLkYnRj5GRy9GS0ZJRkxGTkZQRlJGVC9GV1EsMC4yMjIyMjIyZW1GJy9GWkZYLUZENi1RIi5GJ0Y+RkdGYG9GTEZORlBGUkZURlZGY29GQy1GLDYlRi4tRiM2JC1GLzYlUSJtRidGMkY1Rj5GQEY+

<Text-field style="Heading 2" layout="Heading 2">Recursive representation of multivariate polynomials</Text-field>

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYrLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkobWZlbmNlZEdGJDYnLUYjNigtRiw2I1EhRictRiM2LS1JJW1zdWJHRiQ2JS1GLDYmUSJ4RidGL0YyRjUtRiM2Ji1JI21uR0YkNiVRIjFGJ0YyL0Y2USdub3JtYWxGJ0YyLyUwZm9udF9zdHlsZV9uYW1lR1EpMkR+SW5wdXRGJ0ZOLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSIsRidGMkZOLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRkM2JUZFLUYjNiYtRks2JVEiMkYnRjJGTkYyRlBGTkZTRlYtRlc2LlEjLi5GJ0YyRk5GWi9GZ25GNEZobkZqbkZcb0Zeb0Zgby9GY29RLDAuMjIyMjIyMmVtRicvRmZvRmRvLUZXNi5RIi5GJ0YyRk5GWkZicEZobkZqbkZcb0Zeb0Zgb0Zib0ZlcEZWLUZDNiVGRS1GIzYmLUYsNiZRIm1GJ0YvRjJGNUYyRlBGTkZTRjJGUEZORj1GMkZQRk5GMkZOLyUlb3BlbkdRIltGJy8lJmNsb3NlR1EiXUYnLUZXNi5RIj1GJ0YyRk5GWkZicEZobkZqbkZcb0Zeb0Zgby9GY29RLDAuMjc3Nzc3OGVtRicvRmZvRmpxRistRjk2Jy1GIzYtRkJGVkZob0ZWRl9wRmZwRlYtRkM2JUZFLUYjNihGXXEtRlc2LlEoJm1pbnVzO0YnRjJGTkZaRmJwRmhuRmpuRlxvRl5vRmBvRmNwL0Zmb0ZkcEZKRjJGUEZORlNGMkZQRk5GMkZORmBxRmNxLUY5NictRiM2Ji1GQzYlRkUtRiM2J0ZdcUYvRjJGUEY1RlNGMkZQRk5GMkZORmBxRmNxRjJGUEZOJSFH

f:=x^3*y^2+2*x^2*y^2+3*x*y-4*y;

collect(f,y);

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

We will see other representations as the course progresses

<Text-field bookmark="Polynomial Division" style="Heading 1" layout="Heading 1">Division with remainder</Text-field>

Given LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiLEYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRiw2JlEiZ0YnRi9GMkY1LUY5Ni5RKiZFbGVtZW50O0YnRjJGPEY+L0ZBRjRGQkZERkZGSEZKL0ZNUSwwLjI3Nzc3NzhlbUYnL0ZQRlotRiw2JlEiUkYnRi9GMkY1LUkobWZlbmNlZEdGJDYnLUYjNiUtRiw2JlEieEYnRi9GMkY1RjJGPEYyRjwvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRidGMkY8 with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEiZ0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlErJk5vdEVxdWFsO0YnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTi1JI21uR0YkNiVRIjBGJ0YyRjxGMkY8, find LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYrLUkjbWlHRiQ2JlEicUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiLEYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjk2LlEifkYnRjJGPEY+L0ZBRjRGQkZERkZGSEZKRkwvRlBGTi1GLDYmUSJoRidGL0YyRjUtRjk2LlEqJkVsZW1lbnQ7RidGMkY8Rj5GVUZCRkRGRkZIRkovRk1RLDAuMjc3Nzc3OGVtRicvRlBGaG4tRiw2JlEiUkYnRi9GMkY1LUkobWZlbmNlZEdGJDYnLUYjNiUtRiw2JlEieEYnRi9GMkY1RjJGPEYyRjwvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRidGMkY8 so that

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYwLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEifkYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTkY4LUY5Ni5RIj1GJ0YyRjxGPkZARkJGREZGRkhGSi9GTVEsMC4yNzc3Nzc4ZW1GJy9GUEZVRjgtRiw2JlEicUYnRi9GMkY1RjgtRiw2JlEiZ0YnRi9GMkY1RjgtRjk2LlEiK0YnRjJGPEY+RkBGQkZERkZGSEZKL0ZNUSwwLjIyMjIyMjJlbUYnL0ZQRltvRjgtRiw2JlEiaEYnRi9GMkY1RjJGPA==

and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkjbWlHRiQ2JlEkZGVnRicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYuUSJ+RidGMi9GNlEnbm9ybWFsRicvJSZmZW5jZUdGNC8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZOLUYsNiZRImhGJ0YvRjJGNUY4LUY5Ni5RIjxGJ0YyRjxGPkZARkJGREZGRkhGSi9GTVEsMC4yNzc3Nzc4ZW1GJy9GUEZYRjhGK0Y4LUYsNiZRImdGJ0YvRjJGNUYyRjw=.

Not always possible for all rings LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn.

What if LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiPUYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTi1JJW1zdXBHRiQ2JS1GLDYmUSJ4RidGL0YyRjUtRiM2JS1JI21uR0YkNiVRIjJGJ0YyRjxGMkY8LyUxc3VwZXJzY3JpcHRzaGlmdEdRIjBGJy1GLDYjUSFGJ0YyRjw= and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYrLUkjbWlHRiQ2JlEiZ0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEiPUYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTi1JI21uR0YkNiVRIjJGJ0YyRjwtRjk2LlEifkYnRjJGPEY+RkBGQkZERkZGSEZKL0ZNUSYwLjBlbUYnL0ZQRlktRiw2JlEieEYnRi9GMkY1LUY5Ni5RIitGJ0YyRjxGPkZARkJGREZGRkhGSi9GTVEsMC4yMjIyMjIyZW1GJy9GUEZcby1GUjYlUSIxRidGMkY8RjJGPA== and R=\342\204\244

rem(x^2,-x+1,x);

The division algorithm:

Assume that the leading coefficient of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn is a unit in LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiUkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn (i.e., it has an inverse).

Classical school method: cancel the first coefficient of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn and continue.

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY8LUkjbWlHRiQ2JlEiZ0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEifkYnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTi1GOTYuUSI9RidGMkY8Rj5GQEZCRkRGRkZIRkovRk1RLDAuMjc3Nzc3OGVtRicvRlBGVUY4LUklbXN1YkdGJDYlRistRiM2JS1JI21uR0YkNiVRIjBGJ0YyRjxGMkY8LyUvc3Vic2NyaXB0c2hpZnRHRmluLUY5Ni5RIitGJ0YyRjxGPkZARkJGREZGRkhGSi9GTVEsMC4yMjIyMjIyZW1GJy9GUEZgb0Y4LUZYNiVGKy1GIzYlLUZnbjYlUSIxRidGMkY8RjJGPEZqbi1GLDYmUSJ4RidGL0YyRjVGOEZcb0Y4LUZYNiVGKy1GIzYlLUZnbjYlUSIyRidGMkY8RjJGPEZqbkY4LUklbXN1cEdGJDYlRmlvRl5wLyUxc3VwZXJzY3JpcHRzaGlmdEdGaW5GXG9GOC1GOTYuUSMuLkYnRjJGPEY+RkBGQkZERkZGSEZKRl9vRk8tRjk2LlEiLkYnRjJGPEY+RkBGQkZERkZGSEZKRkxGT0Y4RlxvRjgtRlg2JUYrLUYjNiUtRiw2JlEibUYnRi9GMkY1RjJGPEZqbi1GZHA2JUZpb0ZgcUZmcEYyRjw=

with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkjbW9HRiQ2LlEvJkdyZWF0ZXJFcXVhbDtGJ0YyL0Y2USdub3JtYWxGJy8lJmZlbmNlR0Y0LyUqc2VwYXJhdG9yR0Y0LyUpc3RyZXRjaHlHRjQvJSpzeW1tZXRyaWNHRjQvJShsYXJnZW9wR0Y0LyUubW92YWJsZWxpbWl0c0dGNC8lJ2FjY2VudEdGNC8lJ2xzcGFjZUdRLDAuMjc3Nzc3OGVtRicvJSdyc3BhY2VHRk4tRiw2JlEibUYnRi9GMkY1RjJGPA==.

Look at LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYvLUklbXN1cEdGJDYlLUkjbWlHRiQ2JlEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiYtSShtZmVuY2VkR0YkNiUtRiM2Jy1GLzYmUSJuRidGMkY1RjgtSSNtb0dGJDYuUSgmbWludXM7RidGNS9GOVEnbm9ybWFsRicvJSZmZW5jZUdGNy8lKnNlcGFyYXRvckdGNy8lKXN0cmV0Y2h5R0Y3LyUqc3ltbWV0cmljR0Y3LyUobGFyZ2VvcEdGNy8lLm1vdmFibGVsaW1pdHNHRjcvJSdhY2NlbnRHRjcvJSdsc3BhY2VHUSwwLjIyMjIyMjJlbUYnLyUncnNwYWNlR0Zlbi1JI21uR0YkNiVRIjFGJ0Y1RklGNUZJRjVGSS1GRjYuUSJ+RidGNUZJRktGTUZPRlFGU0ZVRlcvRlpRJjAuMGVtRicvRmduRmBvRjVGSS8lMXN1cGVyc2NyaXB0c2hpZnRHUSIwRictRkY2LlEiPUYnRjVGSUZLRk1GT0ZRRlNGVUZXL0ZaUSwwLjI3Nzc3NzhlbUYnL0ZnbkZpb0Zcb0YuRlxvLUZGNi5RKiZ1bWludXMwO0YnRjVGSUZLRk1GT0ZRRlNGVUZXRllGZm5GXG8tRj42JS1GIzYlLUkmbWZyYWNHRiQ2KC1JJW1zdWJHRiQ2JUYuLUYjNiVGQkY1RkkvJS9zdWJzY3JpcHRzaGlmdEdGZG8tRiM2JS1GZnA2JS1GLzYmUSJnRidGMkY1RjgtRiM2JS1GLzYmUSJtRidGMkY1RjhGNUZJRmpwRjVGSS8lLmxpbmV0aGlja25lc3NHRltvLyUrZGVub21hbGlnbkdRJ2NlbnRlckYnLyUpbnVtYWxpZ25HRlxyLyUpYmV2ZWxsZWRHRjdGNUZJRjVGSS1GLDYlLUYvNiZRInhGJ0YyRjVGOC1GIzYnRkJGRUZlcUY1RklGYm9GXG9GYHFGNUZJ.

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2JlEkZGVnRicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSShtZmVuY2VkR0YkNiUtRiM2JS1JJW1zdXBHRiQ2JS1GLDYmUSJmRidGL0YyRjUtRiM2JS1GOTYlLUYjNictRiw2JlEibkYnRi9GMkY1LUkjbW9HRiQ2LlEoJm1pbnVzO0YnRjIvRjZRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yMjIyMjIyZW1GJy8lJ3JzcGFjZUdGXG8tSSNtbkdGJDYlUSIxRidGMkZQRjJGUEYyRlBGMkZQLyUxc3VwZXJzY3JpcHRzaGlmdEdRIjBGJ0YyRlBGMkZQLUZNNi5RIn5GJ0YyRlBGUkZURlZGWEZaRmZuRmhuL0Zbb1EmMC4wZW1GJy9GXm9Gam8tRk02LlEiPEYnRjJGUEZSRlRGVkZYRlpGZm5GaG4vRltvUSwwLjI3Nzc3NzhlbUYnL0Zeb0ZgcEZmb0ZJRjJGUA== since the highest degree term is cancelled.

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JlEkcmVtRicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYuUSIoRidGMi9GNlEnbm9ybWFsRicvJSZmZW5jZUdGMS8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0YxLyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSwwLjE2NjY2NjdlbUYnLyUncnNwYWNlR0ZOLUYsNiZRImZGJ0YvRjJGNUYyRjw= ,LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkjbW9HRiQ2LlEifkYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGMS8lKGxhcmdlb3BHRjEvJS5tb3ZhYmxlbGltaXRzR0YxLyUnYWNjZW50R0YxLyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGRS1JI21pR0YkNiZRImdGJy8lJ2l0YWxpY0dRJXRydWVGJ0YvL0YzUSdpdGFsaWNGJy1GLDYuUSIpRidGL0YyL0Y2Rk5GNy9GOkZORjtGPUY/RkEvRkRRLDAuMTY2NjY2N2VtRicvRkdGV0YrLUYsNi5RIj1GJ0YvRjJGNUY3RjlGO0Y9Rj9GQS9GRFEsMC4yNzc3Nzc4ZW1GJy9GR0ZnbkYrLUZJNiZRJHJlbUYnRkxGL0ZPLUkobWZlbmNlZEdGJDYlLUYjNigtSSVtc3VwR0YkNiUtRkk2JlEiZkYnRkxGL0ZPLUYjNiUtRl1vNiUtRiM2Jy1GSTYmUSJuRidGTEYvRk8tRiw2LlEoJm1pbnVzO0YnRi9GMkY1RjdGOUY7Rj1GP0ZBL0ZEUSwwLjIyMjIyMjJlbUYnL0ZHRmRwLUkjbW5HRiQ2JVEiMUYnRi9GMkYvRjJGL0YyRi9GMi8lMXN1cGVyc2NyaXB0c2hpZnRHUSIwRictRiw2LlEiLEYnRi9GMkY1L0Y4Rk5GOUY7Rj1GP0ZBRkMvRkdRLDAuMzMzMzMzM2VtRidGK0ZIRi9GMkYvRjItRiw2LlEiLkYnRi9GMkY1RjdGOUY7Rj1GP0ZBRkNGRkYvRjI=

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYwLUkjbWlHRiQ2JlEkcXVvRicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSShtZmVuY2VkR0YkNiUtRiM2Jy1GLDYmUSJmRidGL0YyRjUtSSNtb0dGJDYuUSIsRidGMi9GNlEnbm9ybWFsRicvJSZmZW5jZUdGNC8lKnNlcGFyYXRvckdGMS8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR1EsMC4zMzMzMzMzZW1GJy1GLDYmUSJnRidGL0YyRjVGMkZERjJGRC1GQTYuUSJ+RidGMkZERkYvRklGNEZKRkxGTkZQRlJGVC9GWEZWLUZBNi5RIj1GJ0YyRkRGRkZqbkZKRkxGTkZQRlIvRlVRLDAuMjc3Nzc3OGVtRicvRlhGYG9GZ24tRjk2JS1GIzYlLUkmbWZyYWNHRiQ2KC1JJW1zdWJHRiQ2JUY9LUYjNiUtRiw2JlEibkYnRi9GMkY1RjJGRC8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYnLUYjNiUtRmpvNiVGWi1GIzYlLUYsNiZRIm1GJ0YvRjJGNUYyRkRGYXBGMkZELyUubGluZXRoaWNrbmVzc0dRIjFGJy8lK2Rlbm9tYWxpZ25HUSdjZW50ZXJGJy8lKW51bWFsaWduR0ZicS8lKWJldmVsbGVkR0Y0RjJGREYyRkQtSSVtc3VwR0YkNiUtRiw2JlEieEYnRi9GMkY1LUYjNidGXnAtRkE2LlEoJm1pbnVzO0YnRjJGREZGRmpuRkpGTEZORlBGUi9GVVEsMC4yMjIyMjIyZW1GJy9GWEZjckZqcEYyRkQvJTFzdXBlcnNjcmlwdHNoaWZ0R0ZjcEZnbi1GQTYuUSIrRidGMkZERkZGam5GSkZMRk5GUEZSRmJyRmRyRistRjk2JS1GIzYoLUZocTYlRj0tRiM2JS1GOTYlLUYjNidGXnBGX3ItSSNtbkdGJDYlRl9xRjJGREYyRkRGMkZERjJGREZlckZARmduRlpGMkZERjJGRC1GQTYuUSIuRidGMkZERkZGam5GSkZMRk5GUEZSRlRGW29GMkZE

Here it is in Maple:

f:=x^5-3*x^4+2*x^3-2*x^2+5*x+1;

g:=x^3+2*x^2-5*x+4;

c:=lcoeff(f,x)/lcoeff(g,x)*x^(degree(f,x)-degree(g,x));

ff4:=expand(f-c*g);

rem(f,g,x);

rem(ff4,g,x);

quo(f,g,x);

quo(ff4,g,x);

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

Try it when the leading coefficient of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JlEiZ0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjIvRjZRJ25vcm1hbEYn is not \302\2611.

What does division with remainder mean for multivariate polynomials?

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

JSFH