Go Back > Math Stuff > Abstract Algebra & Algebraic Number Theory

Thread Tools
Old 2018-05-21, 03:11   #1
May 2018

1 Posts
Default [Help] understanding about finding norm in non monic polynomials

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?
canny is offline   Reply With Quote
Old 2018-05-22, 07:17   #2
Nick's Avatar
Dec 2012
The Netherlands

22×19×23 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.
\[ 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
Nick is online now   Reply With Quote

Thread Tools

Similar Threads
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

All times are UTC. The time now is 17:54.

Fri Oct 22 17:54:20 UTC 2021 up 91 days, 12:23, 0 users, load averages: 1.90, 1.54, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.