Re: Need Help with Quadratic Sieve

From: Brian Gladman (brg_at_nowhere.at.all)
Date: 03/28/04

  • Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public" 
    Date: Sun, 28 Mar 2004 17:30:50 +0100

    "Korejwa" <korejwa@tiac.net> wrote in message
    news:opr5jtg31myzibhw@news.west.earthlink.net...
    >
    > I am trying to write code for the basic Quadratic Sieve factoring
    > algorithm.
    >
    > After defining the factor base and sieving interval, there is a method for
    > simultaneously testing multiple numbers in the sieving interval for
    > smoothness, avoiding the need for trial division.
    >
    > Could someone please explain this part of the algorithm? I know it
    > involves the Shanks-Tonelli algorithm, which I understand and can
    > implement. Any help is much appreciated.

    There is a paper on-line here that you may find helpful:

      http://www.math.uiuc.edu/~landquis/quadsieve.pdf

    Scott Contini's FactorWorld page is also a good starting point for factoring
    information:

      http://www.crypto-world.com/FactorWorld.html

        Brian Gladman

  • Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"

    Relevant Pages

    • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
      ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
      (sci.crypt)
    • Re: Ultimate check, new way to factor or not?
      ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
      (sci.crypt)
    • Re: I was right, surrogate factoring proof
      ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
      (sci.math)
    • Re: I was right, surrogate factoring proof
      ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
      (sci.crypt)
    • Re: More math stuff, truth and social reality
      ... > out that I use brainstorming, where you generate lots of ideas during ... fast as other efficient factoring algorithms. ... I don't see evidence of lying, ... algorithm) is in fact the truth. ...
      (sci.math)