20150119, 01:41  #1 
Sep 2011
3·19 Posts 
NFS: Sieving the norm over ideals vs. integers
Hello, me again lol.
In Briggs paper, I am told to find prime ideals (r,p) such that f(r) = 0 mod p, and each prime ideal is "responsible" for dividing the norm, that is, each prime ideal has an entry on the matrix. Currently, my implementation instead just uses primes in Z to sieve the norm, so the norms are smooth over Z primes, and each prime has an entry on the matrix. Is there a difference between two approaches? Some NFS papers say that I'm supposed to look for smooth norms, others say it has be smooth over prime ideals. Is the splitting of primes to different prime ideals just another technique to keep the sieved values smaller (since one prime is used multiple times), or will it break the algorithm if this isn't done? Last fiddled with by paul0 on 20150119 at 01:42 
20150119, 05:46  #2 
Sep 2011
111001_{2} Posts 
I just read Pomerance again, it turns out that no, the two are not equivalent. It's an explicit example in page 283. You can ignore this post now, I apologize.

20150119, 11:52  #3 
Tribal Bullet
Oct 2004
3×7×13^{2} Posts 
You found this out, but ideals matter because each individual ideal must occur an even number of times during the NFS algebraic square root, not just the prime that the ideal lies over. If the norm of a given relation contains a factor p, only one of the ideals over p in the algebraic factor base gets its count incremented. For an algebraic polynomial of degree d there are as many as d different entries in the algebraic factor base for each prime p, and you must sieve them individually.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
norm vs size  chris2be8  Msieve  1  20150913 02:24 
Factorization of Ideals in Number Field, Looking for Reference  jinydu  Abstract Algebra & Algebraic Number Theory  5  20140730 11:24 
Theorems about ideals  fivemack  Abstract Algebra & Algebraic Number Theory  10  20120122 11:01 
Counting ideals during singleton removal  fivemack  Factoring  5  20071230 11:17 
NFS and smooth norm MOD N ?  bonju  Factoring  9  20050826 13:29 