Timeline for In the Quadratic Sieve, why restrict the factor base?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 28, 2016 at 15:00 | comment | added | fgrieu♦ | @Mok-Kong Shen: your remark helped me fix a serious mistake in the question: I had written $\left({p\over N}\right)=+1$ which requires the Jacobi symbol, rather than $\left({N\over p}\right)=+1$ which is fine with just the Legendre symbol, and is a different filter. Also, your HAC reference helped find a partial answer. Thanks! | |
| May 28, 2016 at 7:32 | comment | added | Mok-Kong Shen | (As an aside, your link to Wolfram says Legendre symbol, not Jacobi symbol.) HAC 3.2.6 says "Thus the factor base need only contain those primes p for which the Legendre symbol (n/p) is 1", Doesn't that fully answer your question? | |
| May 27, 2016 at 13:46 | comment | added | Robert NACIRI | @fgrieu Right! But some strategies are more or less effective than others. Recall that the main objective is that $\prod Q(x_i)=v^2$ is QR, independantly of each $x_i$ in order to satisfy $\prod x_i^2-v^2=0$ [n] | |
| May 27, 2016 at 11:39 | comment | added | fgrieu♦ | So why is it customary to restrict a factor base to QR in any serious implementation or article? | |
| May 27, 2016 at 11:01 | history | answered | Robert NACIRI | CC BY-SA 3.0 |