Transcript Extractors from Polynomials

R.Shaltiel and C.Umans
1
Definitions
Def (min-entropy): The min-entropy of a random
variable X over {0, 1}n is defined as:
H  X 
Minn log2 Pr X  x 
x0,1
Thus a random variable X has min-entropy at
least k if Pr[X=x]≤2-k for all x. The maximum
possible min-entropy for such a R.V. is n
Def (statistical distance): Two distributions on
a domain D are e-close if the probabilities
they give to any AD differ by at most e
(namely, using norm 1)
2
Definitions
Def (extractor): A (k,e)-extractor is a function
E: 0,1n  0,1t  0,1m
s.t. for any R.V. X with min-entropy ≥k
E(X,Ut) is e-close to Um
(where Um denotes the uniform distribution over 0,1m)
Weak random source
n
Seed
t
E
Random string
m
3
Parameters
The relevant parameters are:
 min entropy of the weak random source input – k.
Relevant values log(n) k  n
(the seed length is t ≥ log(n),
hence useless to consider lower min entropy).



seed length t ≥ log(n) .
Quality of the output: e.
Size of the output m=f(k). The optimum is m=k.
Weak random source
n
Seed
t
E
Random string
m
4
Extractors
High
Min-Entropy
distribution
Uniform-distribution
seed
2t
2n
E
2m
Close to uniform
output
5
Next Bit Predictors
Claim: to prove E is an extractor, it suffices to
prove that for all 0<i<m+1 and all predictors
f:0,1i-10,1
1 e


Pr f E  X,Ut 1...i1  E  X,Ut i  

 2 m
Proof: Assume E is not an extractor; then
exists a distribution s.t. X s.t. E(X,Ut) is not
e-close to Um, that is:


A  0,1
m
P
Pr E  x, s   A  Pr  y  A  e
s~Ut ,x~X
y~Um
6
Proof
Now define the following hybrid distributions:
H0  Um
H1  E  X,Ut 1 Um1
...
Hi1  E  X,Ut 1..i1 Umi1
Hi  E  X,Ut 1..i Umi
...
Hm  E  X,Ut 1..m
7
Proof
Summing the probabilities for the event corresponding
to the set A for all distributions yields:
m
 Pr x  A 
i 0
x~Hi
Pr x  A 
x~Hi 1
 Pr  x  A  Pr x  A  P  ε
x~Hm
x~H0
And because |∑ai|≤ ∑|ai| there exists an index 0<i<m+1
for which:
H(A)
 Hi1 (A)
i
Pr x  A  Pr x  A 
x~Hi 1
x~Hi
e
m
8
The Predictor
We now define a function f:0,1i-1  0,1 that
can predict the i’th bit with probability at
least ½+e/m (“a next bit predictor”):
The function f uniformly and independently
draws the bits yi,…,ym and outputs:
 yi  x1 ,..., xi1 , yi ..., ym  A
f  x1 ,..., xi1   
yi  otherwise

Note: the above definition is not constructive,
as A is not known!
9
Proof
And f is indeed a next bit predictor:
Pr f  x1 ...xi1   xi  
Pr  x1 ...xi1 yi ...ym  A    yi  xi    Pr  x1 ,..., xi1, yi,...ym  A    yi  xi   
Pr  x1 ...xi1xi yi1 ...ym  A   yi  xi    1  Pr  x1 ,..., xi1 , yi,...ym  A    yi  xi   
1
1 1


Hi  A  1  Hi1  A   Hi A   
2
2 2


1
1 e
 Hi  A  Hi1  A  
2
2 m
Q.E.D.
10
Basic Example –
Safra, Ta-Shma, Zukerman
Construction:
 Let BC:F{0,1}s be a (inefficient) binary-code
 Given



x, a weak random source, interpreted as a
polynomial x:F2F and
s, a seed, interpreted as a random point (a,b), and
an index j to a binary code.
Def:
E  x,s   BC  x  a,b  j ,BC  x  a,b  1 j ,...,BC  x  a,b  m j
11
Basic Example –
Illustration of Construction

x  x, s = ((a,b), 2)
(a,b)
(a,b+1)
(a,b+m)
x(a,b)
x(a,b+1)
x(a,b+m)
001

110
000
E(x,s)=01001
101
(inefficient)
binary code
110
12
Basic Example –
Proof Sketch

Assume, by way of contradiction:
exists a next bit predicator function f.
 12
Pr E  X,Ut i  f E  X,Ut 1...i1    l


Next, show a reconstruction function R
Pr z.Rf (z)  x   1 2



x X

Conclude, a contradiction!
(to the min-entropy assumption of X)
13
Basic Example –
Reconstruction Function
h ~ n1/2
j ~ lgn
m ~ desired entropy
“advice”
Random
“Few” red
line
points:
a=mjO(h)
Repeat using the
List
decoding
Resolve
into by
one
new points, until all
the
predictor
f
value
on the line
Fd is evaluated
14
Counting Argument
For Y  X, let (Y)=yYPr[y] (“the weight of Y”)
Let R:{0,1}a  0,1n, s.t.
Prx~X[z R(z)=x]  1/2
 (for a uniform X, |R(S)|  |X|/2 )
 For an arbitrary distribution X, (R(S))  (X)/2
 Let X ~ min-entropy  k,

then (R(S))  2a-k

and therefore k  a - log2(1/2)
(there are at most 2a strings in R(S), and xX Pr[x]  2-k)
(1 = (X)  (R(S)) 2  2a-k 2
-1  a-k hence k  a+1)
R
S
R(S)
2a
X
2n
15
Problems with
Safra, Ta-Shma, Zukerman

Curse of dimensionality - too many lines!
Solution: generator matrix.
16
Next-q-it List-Predictor
f is allowed to output a small list of l
possible next elements
17
q-ary Extractor
Def: Let F be a field with q elements.
A (k, l) q-ary extractor is a function
E: 0,1n  0,1t Fm
s.t. for all R.V. X with min-entropy ≥k
and all 0<i<m
and all list-predictors f:Fi-1  Fl


Pr E  X,Ut i  f E  X,Ut 1...i1    1
l
18
Generator Matrix
Def: Define the generator matrix for the
vector space Fd as a matrix Ad×d, s.t. for
any non-zero vector vFd:
A v
i
i
 F \ 0
d
(that is, any vector 0≠vFd multiplied by all
powers of A generates the entire vector
space Fd except for 0)
Lemma: Such a generator matrix exists and can
be found in time qO(d).
19
Construction




Let F be a field with q elements,
Let Fd be a vector space over F.
h  d
n



Let h be the smallest integer s.t.
d
log q


For x 0,1n, let x denote the unique d-variate
polynomial of total degree h-1 whose coefficients are
specified by x.
Note that for such a polynomial, the number of
coefficients is exactly:  h d d   logn q
(“choosing where to put d-1 bars between h-1 balls”)
20
Construction

The definition of the q-ary extractor:
E: 0,1n  0,1d log q  Fm
E  x, v   x  v  , x A v  , x A v ,..., x A v 
1
seed,
interpreted as a
vector v Fd
2
Generator
matrix
x(Aiv)
x(v)
v
Amv
x(Amv)
Aiv
m
Amv
Fd
Aiv
v
21
Main Theorem
Thm: For any n,q,d and h as previously
defined, E is a (k, l) q-ary extractor if:
k    mhdlogq  log
 l
q   h2d2l2 
Alternatively, E is a (k, l) q-ary extractor if:
k    mhdlog2 q   log
q   l2hdlog q 
 l
22
What’s Ahead






Proving existence of a generator matrix
How the counting argument works
The reconstruction paradigm
Basic example – Safra, Ta-Shma, Zukerman
Proof of the main theorem
From extractors to PRGs
23
Extension Fields
A field F2 is called an extension of another field F if F
is contained in F2 as a subfield.
Thm: For every power pk (p prime, k>0) there is a unique
(up to isomorphism) finite field containing pk
elements. These fields are denoted GF(pk).
All finite fields’ cardinality have that form.
Def: A polynomial is called irreducible in GF(p) if it does
not factor over GF(p)
Thm: Let f(x) be an irreducible polynomial of degree k
over GF(p). The finite field GF(pk) can be constructed
using the set of degree k-1 polynomials over Zp, with
addition and multiplication carried out modulo f(x)
24
Extension Fields - Example
Construct GF(25) as follows:
Let the irreducible polynomial be: f ( x)  x 4  x3  x 2  x  1
Represent every k degree polynomial as a vector of k+1
coefficient:
f ( x)  x 4  x3  x 2  x  1  (1,1,1,1,1)
Addition over this field:
( x 4  x 3  x  1)
 ( x 3  x 2  x  1)

(1,1,0,1,1)
 (0,1,1,1,1)
________
(1,0,1,0,0)
25
Extension Fields - Example
And multiplication:

( x 4  x 3  x  1)
 ( x  x  1)
3
x7  x6  x5  x 4  x 2  1

And now modulo the irreducible polynomial:
x7  x6  x5  x 4  x 2  1
mod
x 4  x3  x 2  x  1

(1,1,0,1,1)
 (0,1,0,1,1)
_________
11011
11011 _
00000 __
 11011 ___
_________
11110101
( x 4  x3  1)
26
Generator Matrix –
Existence Proof
Denote by GF*(qd) the multiplicative group of
the Galois Field GF(qd).
This multiplicative group of the Galois Field is
cyclic, and thus has a generator g:
g | 0  i  q   GF  q 
i
d
*
d
Let j be the natural isomorphism between the
Galois Field GF(qd) and the vector space Fd,
which matches a polynomial with its vector of
coefficients:
j(x4  x3  x  1)  (1,1,0,1,1)
27
Generator Matrix –
Existence Proof
Now define the generator matrix A of Fd as the linear
transformation that corresponds to multiplication by
the generator in GF*(qd) :
d
1
u  F .Au  j  g  j u  
A is a linear transformation because of the distributive
property of both the vector space and the field
GF(qd), according to the isomorphism properties:
A  u1  u2   j  g  x   f  x   h  x   
 j  g  x   f x   g x   h x 
 j  g  x   f x   j g x   h x 
 A  u1   A  u2 
28
Generator Matrix –
Existence Proof
It remains to show that the generator matrix A of Fd
can be found in time qO(d).
And indeed:
 The Galois Field GF(qd) can be constructed in time
qO(d) using an irreducible polynomial of degree d over
the field Zq (and such a polynomial can also be found
in time qO(d) by exhaustive search).
 The generator of GF(qd) can be found in time qO(d) by
exhaustive search
 Using the generator, for any basis of Fd, one can
construct d independent equations so as to find the
linear transformation A. This linear equation system
is also solvable in time qO(d) .
29
“Reconstruction Proof Paradigm”
Proof sketch:
For a certain R.V. X with min-entropy at least k,
assume a function f that violates the properties of a qary extractor,
construct another function, R :0,1a  0,1n, the
“reconstruction function”.
This function, using f as a procedure, has the property
that:
f

Pr z.R z   x   1 2
x~X
Applying the “counting argument”, this is a contradiction
to the assumption that X has min-entropy at least k
30
Proof Sketch


Let X be a random variable with min-entropy
at least k
Assume, by way of contradiction:
exists a next bit predicator function f.


 12
Pr E  X,Ut i  f E  X,Ut 1...i1    l



Next, show a reconstruction function R
Pr z.Rf z   x   1 2
x X

Conclude, a contradiction!
(to the min-entropy assumption of X)
31
Main Lemma
Lemma: Let n,q,d,h be as in the main theorem.
There exists a probabilistic function
R:0,1a0,1n with a = O(mhd logq) such
that for every x on which:
 12


Pr j.f E  x, y 1...i1  E  x, y i  1 2  l

j
y 



The following holds (the probability is over the
random coins of R):
1
Pr z.R  z   x  
2
f
32
The Reconstruction Function (R)


Task: allow many strings x in the support of X
to be reconstructed from very short advice
strings.
Outlines:



Use f in a sequence of prediction steps
to evaluate z on all points of Fd,.
Interpolate to recover coefficients of z,
which gives x
Next We Show: there exists a sequence of
prediction steps that works for many x in the
support of X and requires few advice strings
33
Curves


Let r=Q(d),
Pick random vectors and values



Define degree 2r-1 polynomials p1,p2




2r random points y1,…,y2rFd, and
2r values t1,…,t2rF, and
p1:FFd defined by p1(ti)=yi, i=1,..,2r.
p2:FFd defined by p2(ti)=Ayi, i=1,..,r, and
p2(ti)=yi, i=r+1,..,2r.
Define vector sets P1={p1(z)}zF and
P2={p2(z)}zF
i>0 define P2i+1=AP2i-1 and P2i+2=AP2i
({Pi}, the sequence of prediction steps are low-degree
curves in Fd, chosen using the coin tosses of R)
34
Am v
Curves
i*(y
Ai*
(y22))
Ai*(yr+1)
Ai*i*(y11)
A3(y
2
)
i*(y
Ai*
(yrr))
Aiv
Ai*(y2r)
v
Ai*-1(yr+1))
Fd
Amv A3(y1)
A2(y 2)
A3(yr)
A2(yr+1)
r+1))
A2(y1)
A(y2)
2(y )
A
A(y
rr)
A(yr+1)
r+1))
A(yr)
A(y1)
Ai*-1(y2r)
A
A22(y
(y2r
)
2r)
A(y2r
)
A(y
2r)
y2
Aiv
v
yr+1
y1
yr
y2r
t1 t2
tr tr+1
t2r
F
35
Simple Observations

A is non-singular linear-transform, hence i





Pi is 2r-wise independent collection of points
Pi and Pi+1 intersect at r random points
z|Pi is a univariate polynomial of degree at most
2hr.
Given evaluation of z on Av,A2v,…,Amv, we may
use the predictor function f to predict
z(Am+1v) to within l values.
We need advice string: 2hr coefficients of z|Pi
for i=1,…,m.
(length: at most mhr log q ≤ a)
36
Using N.B.P.
i*(y
Ai*
(y22))
Ai*i*(y11)
A3(y2)
Ai*(yr+1)
i*(y
Ai*
(yrr))
Ai*(y2r)
Cannot resolve into one
value!
Ai*-1(yr+1))
Fd
Amv A3(y1)
A2(y 2)
A3(yr)
A2(yr+1)
r+1))
A2(y1)
A(y2)
2(y )
A
A(y
rr)
A(yr+1)
r+1))
A(yr)
A(y1)
Ai*-1(y2r)
A
A22(y
(y2r
)
2r)
A(y2r
)
A(y
2r)
y2
Aiv
v
yr+1
y1
yr
y2r
t1 t2
tr tr+1
t2r
F
37
Ai*+1(y2)
Ai*+1(y1)
i*(y
Ai*
(y22))
Ai*i*(y11)
A3(y2)
Using N.B.P.
Ai*+1(yr)
Ai*(yr+1)
i*(y
Ai*
(yrr))
Can resolve into one
value using the second
curve!
Ai*(y2r)
Ai*-1(yr+1))
Fd
Amv A3(y1)
A2(y 2)
A3(yr)
A2(yr+1)
r+1))
A2(y1)
A(y2)
2(y )
A
A(y
rr)
A(yr+1)
r+1))
A(yr)
A(y1)
Ai*-1(y2r)
A
A22(y
(y2r
)
2r)
A(y2r
)
A(y
2r)
y2
A iv
v
yr+1
y1
yr
y2r
t1 t2
tr tr+1
t2r
F
38
Ai*+1(y2)
yr+1
Ai*+1(y1)
i*(y
Ai*
(y22))
Ai*i*(y11)
A3(y2)
Ai*+1(yr)
Ai*(yr+1)
i*(y
Ai*
(yrr))
y2r
Using N.B.P.
Can resolve into one
value using the second
curve!
Ai*(y2r)
Ai*-1(yr+1))
Fd
Amv A3(y1)
A2(y 2)
A3(yr)
A2(yr+1)
r+1))
A2(y1)
A(y2)
2(y )
A
A(y
rr)
A(yr+1)
r+1))
A(yr)
A(y1)
Ai*-1(y2r)
A
A22(y
(y2r
)
2r)
A(y2r
)
A(y
2r)
y2
A iv
v
yr+1
y1
yr
y2r
t1 t2
tr tr+1
t2r
F
39
Main Lemma Proof Cont.

Claim: with probability at least 1-1/8qd over the
coins tosses of R:


Pr j.f x Ai*1z ,..., x A1z 
zPi 


1

j  x z  
 4 l
Proof: We use the following tail bound:
Let t>4 be an even integer, and X1,…,Xn be t-wise
independent R.V. with values in [0,1]. Let X=Xi, 2 t / 2
=E[X], and A>0. Then: Pr  X    A  8   t  t 


2
A


40
Main Lemma Proof Cont.
According to the next bit predictor, the probability
for successful prediction is at least 1/2√l.
 In the i’th iteration we make q predictions (as many
points as there are on the curve).
 Using the tail bounds provides the result.
Q.E.D (of the claim).

Main Lemma Proof (cont.): Therefore, w.h.p. there are
at least q/4√l evaluations points of Pi that agree
with the degree 2hr polynomial on the i’th curve (out
of a total of at most lq).
41
Main Lemma Proof Cont.


A list decoding bound: given n distinct pairs (xi,yi) in
field F and Parameters k and d, with k>(2dn)1/2,
There are at most 2n/k degree d polynomials g such
that g(xi)=yi for at least k pairs.
Furthermore, a list of all such polynomials can be
computed in time poly(n,log|F|).
Using this bound and the previous claim, at most
8l3/2 degree 2rh polynomials agree on this number of
points (q/4√l ).
42
Lemma Proof Cont.

Now,




Pi intersect Pi-1 at r random positions, and
we know the evaluation of z at the points in Pi-1
Two degree 2rh polynomials can agree on at most
2rh/q fraction of their points,
So the probability that an “incorrect” polynomial
among our candidates agrees on all r random points
in at most
(8l
3/ 2
2rh r
1
)(
)  d
q
8q
43
Main Lemma Proof Cont.

1
So, with probability at least 1
8q d
we learn points Pi successfully.
 After 2qd prediction steps, we have learned
z on Fd\{0} (since A is a generator of Fd\{0})
 by the union bound, the probability that
every step of the reconstruction is
successful is at least ½.
Q.E.D (main lemma)
44
Proof of Main Theorem Cont.


First, Pr [j. f ( E ( x, y )1... i*1 ) j  E ( x, y )i* ]  1 / l
x X , y
By averaging argument:


Pr Pr j. f ( E ( x, y)1... i*1 ) j  E ( x, y)i*  1 / 2 l   1 / 2 l

x X 
y

Therefore, there must be a fixing of
the coins of R, such that:


1 1
1
Pr z.R ( z )  x  

x X
2 2 l 4 l
f
45
Ai*+1(y2)
Ai*+1(y1)
i*(y
Ai*
(y22))
Ai*i*(y11)
A3(y2)
Using N.B.P. – Take 2
Ai*+1(yr)
Ai*(yr+1)
i*(y
Ai*
(yrr))
Unse N.B.P over all
points in F, so that we
get enough ”good
evaluation”
Ai*(y2r)
Ai*-1(yr+1))
Fd
Amv A3(y1)
A2(y 2)
A3(yr)
A2(yr+1)
r+1))
A2(y1)
A(y2)
2(y )
A
A(y
rr)
A(yr+1)
r+1))
A(yr)
A(y1)
Ai*-1(y2r)
A
A22(y
(y2r
)
2r)
A(y2r
)
A(y
2r)
y2
A iv
v
yr+1
y1
yr
y2r
t1 t2
tr tr+1
t2r
F
46
Proof of Main Theorem Cont.



According to the counting argument, this implies
that:


k  log( )  advice  log( )  O(2mhr log q)
4
4
Recall that r=Q(d).
A contradiction to the parameter choice:
1
k  (mhd log q)  log( )
l
Q.E.D (main theorem)!
47
48
From q-ary extractors to
(regular) extractors
The simple technique - using error correcting codes:
Lemma: Let F be a field with q elements. Let
C:0,1k=log(q)0,1n be a binary error correcting
code with distance at least 0.5-O(2) . If
E: 0,1n *0,1t  Fm is a (k,O()) q-ary extractor, then
E’: 0,1n *0,1t+log(n)  Fm defined by:
E'(x;(y, j))  C(E(x;y)1 )j ... C(E(x;y)m )j
Is a (k,m) binary extractor.
49
From q-ary extractors to
(regular) extractors
A more complex transformation from q-ary extractors
to binary extractors achieves the following
parameters:
Thm: Let F be a field with q<2m elements. There is a
polynomial time computable function:
logqlog* m
O(log
)

1
(mlog )

B:
F

{0,1}

{0,1}
Such that for any (k,) q-ary extractor E,
m
E’(x;(y,j))=B(E(x;y),j) is a (k, log*m) binary extractor.
50
From q-ary extractors to
(regular) extractors
The last theorem allows using theorem 1
for  = O(e/log*m) , and implies a (k,e)
extractor with seed length t=O(log n)
and output length m=k/(log n)O(1)
51
Extractor  PRG

Identify:


string x{0,1}log n with the
function x:{0,1}log n{0,1} by setting x(i)=xi
Denote by S(x) the size of the smallest circuit
computing function x
Def (PRG): an -PRG for size s is a function
G:{0,1}t{0,1}m with the following property: 1im
and all function f:{0,1}i-1{0,1}i with size s circuits,
Pr[f(G(Ut)1...i-1)=G(Ut)i]  ½ + e/m
This imply:
for all size s-O(1) circuits C
|Pr[C(G(Ut))=1] – Pr[C(Um)=1]| e

52
q-ary PRG
Def (q-ary PRG): Let F be the field with q
elements. A -q-ary PRG for size s is a
function G:{0,1}tFm with the following
property: 1im and all function f:Fi-1F(-2)
with size s circuits,
Pr[j f(G(Ut)1...i-1)j=G(Ut)i]  
Fact: O()-q-ary PRG for size s can be
transformed into (regular) m-PRG for size
not much smaller than s
53
(j) corresponds to using our q-ary extractor
Note:
G
x
We show:
mj
(j)
construction
with
the
“successor
function”
A
x is hard  at least one Gx is a q-ary PRG
The Construction
Plan for building a PRG Gx:{0,1}t  {0,1}m:
 use a hard function x:{0,1}log n  {0,1}
 let z be the low-degree extension of x
 obtain l “candidate” PRGs, where l=d(log
q / log m) as follows:
(j):{0,1}d log q  Fm by
For 0j<l define
G
x
j
j
j
(j)
1m
2m
Mm
Gx (v) = z(A v)  z(A v) ... z(A
v)
where A is a generator of Fd\{0}
54
Getting into Details
d as both a vector space and the
think
of
F
d
Note F’ is a subset of Fd
perhaps we
should
extension
field
of Fjust say: immediate from
the correspondence between the cyclic group
GF(qd) and Fd\{0} ??? otherwise in details we
Let
may F’
say:be a subfield of F of size h
Proof:
Lemma:
there exist invertible dd
There
existsA
a natural
matrices
and A’correspondence
with entries from
d and GF(qd), and between F’d and
between
F
which
satisfy:
d
GF(h ), d
iv} =Fd\{0}
  vF
s.t.
v0,
{A
i i.e. there
GF(qd) is cyclic of order qd-1,
d s.t. v0,
a generator
g {A’iv}i=F’d\{0}
exists
 vF’
d-1)/(h
d-1) of order
gp generates
unique
subgroup
 A’=Ap for the
p=(q
hd-1, the multiplicative group of GF(hd).
 A and A’ can be found in time qO(d)
A and A’ are the linear transforms
corresponding to g and gp respectively.
F
55
since hd>n, there are enough “slots” to embed
Note
h denotes the
individual
The
computation
of zdegree
from xincan
beddone in
all x in a d dimensional cube of size h
d)=qand
O(d) the
variables,
total degree
is at most hd
poly(n,q
time
d
and since A’ generates F’ \{0}, indeed x is
embedded in a d dimensional cube of size hd
require hd>n
 Define z as follows z(A’i1)=x(i), where 1 is the
all 1 vector (low degree extension).
 Recall: For 0j<l define Gx(j):{0,1}d log q  Fm by
j
j
j
(j)
1m
2m
Mm
Gx (v) = z(A v)  z(A v) ... z(A
v
Theorem (PRG main): for every n,d, and h
satisfying hd>n, at least one of Gx(j) is an -qary PRG for size (-4 h d2 log2q).
Furthermore, all the Gx(j)s are computable in
time poly(qd,n) with oracle access to x.

56

e
57
58
Extension Field
Def: if F is a subset of E, then we say
that E is an extension field of F.
Lemma: let
 E be an extension field of F,
 f(x) be a polynomial over F (i.e. f(x)F[X]),
 cE,
then f(x)f(c) is an homomorphism of
F[X] into E.
59
Construction of the Galois Field
GF(qd)
Thm: let p(x) be irreducible in F[X], then
there exists E, an extension field of F,
where there exists a root of p(x).
Proof Sketch:
 add a  (a new element) to F.
 is to be a root of p(x).
 In F[] (polynomials with variable )
60



Example:
F=reals
p(x)=x2+1
61