![]() |
![]() |
#1 |
"chun"
May 2018
Indonesia
1 Posts |
![]()
Hi, I'm interested in algorithm, namely NFS (number field sieve).
So, the problem is that we're trying to sieve over the norm generated by a,b pairs in the form of algebraic number that is in the form of (a - bα) where α is the algebraic root of irreducible polynomial f. Say, in most of the references i've read, it's said that the norm will be F (a,b) = b^d*f(a/b). And as for monic polynomial, the norm isn't changing. However, if the polynomial isn't monic (say leading coefficient is some constant C), then the norm calculation would be different, in this case it will be N(a - bα) = (F(a,b))/c. I just wanted to make sure, is this true? |
![]() |
![]() |
![]() |
#2 |
Dec 2012
The Netherlands
41×43 Posts |
![]()
Let R be a UFD with K its field of fractions and f in R[X] monic and irreducible of degree n≥1.
Let α be in an algebraic closure of K satisfying f(α)=0. Then \[ 1,\alpha,\alpha^2,\ldots,\alpha^{n-1} \] is a basis for R[α] over R. Now take any r,s in R with s≠0 and let g be the function from R[α] to R[α] given by g(x)=(r+sα)x. By calculating the matrix for g relative to the above basis, we see that the norm (from R[α] to R) of r+sα is given by \[ (-s)^nf\left(\frac{-r}{s}\right)\] If f is not monic, then the first step fails already. Last fiddled with by Nick on 2018-05-22 at 07:18 Reason: Typo |
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
Understanding NFS | Demonslay335 | YAFU | 11 | 2016-01-08 17:52 |
norm vs size | chris2be8 | Msieve | 1 | 2015-09-13 02:24 |
NFS: Sieving the norm over ideals vs. integers | paul0 | Factoring | 2 | 2015-01-19 11:52 |
Finding all divisors kn + 1 of P(n) for various polynomials P | Drdmitry | Computer Science & Computational Number Theory | 0 | 2014-11-28 14:51 |
NFS and smooth norm MOD N ? | bonju | Factoring | 9 | 2005-08-26 13:29 |