Go Back > Factoring Projects > Factoring

Thread Tools
Old 2015-01-19, 01:41   #1
Sep 2011

3×19 Posts
Default 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 2015-01-19 at 01:42
paul0 is offline   Reply With Quote
Old 2015-01-19, 05:46   #2
Sep 2011

5710 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.
paul0 is offline   Reply With Quote
Old 2015-01-19, 11:52   #3
Tribal Bullet
jasonp's Avatar
Oct 2004

3·1,181 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.
jasonp is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
norm vs size chris2be8 Msieve 1 2015-09-13 02:24
Factorization of Ideals in Number Field, Looking for Reference jinydu Abstract Algebra & Algebraic Number Theory 5 2014-07-30 11:24
Theorems about ideals fivemack Abstract Algebra & Algebraic Number Theory 10 2012-01-22 11:01
Counting ideals during singleton removal fivemack Factoring 5 2007-12-30 11:17
NFS and smooth norm MOD N ? bonju Factoring 9 2005-08-26 13:29

All times are UTC. The time now is 07:49.

Tue Aug 3 07:49:14 UTC 2021 up 11 days, 2:18, 0 users, load averages: 2.17, 2.23, 2.30

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.