AdamWhiteHat/GNFS

What mean Smoothness Bound

SlimRG opened this issue · 2 comments

SlimRG commented

Can you give more info about variables!
Thanks!

AdamWhiteHat commented

Good question. Ill probably include these as tool-tips in the GUI in the next day or two.

I hope this helps. If you have any more follow up questions, just ask.

N

This is the number to factor. It should be a semi-prime. Also called the modulus in an RSA key (despite it not actually being a modulus in the mathematical sense).

Smoothness Bound

  • A bound on primes.
  • Primes will be generated up to this number.
  • A candidate will be considered 'smooth' if its prime factorization contains only primes below this bound.
  • This number defines what it is to be smooth.

Polynomial base

This is the X in the following polynomial: 1X^3 + 15X^2 + 29X^1 + 8X^0

Polynomial degree

The maximum exponent of a polynomial. For the polynomial: 1X^3 + 15X^2 + 29X^1 + 8X^0, the degree is 3.

Relation quantity

The number of relations to find before attempting the matrix step.

Relation value range

This defines a number, call it A, defines a range from -A to +A in the relation equation:
A + B*X

AdamWhiteHat commented

I understand that this application is not very user friendly. It requires someone who understands the General Number Field Sieve algorithm.

For me to explain where the polynomial comes from and what it is for is to repeat whats already in the literature.

Check out the .PDF files that are in the root directory of the master branch of this project. Any one of the PDFs should cover the algorithm in depth; just choose the one that is easiest for you to read.

BUT... Before you learn the GNFS algorithm, you should learn the quadratic sieve first.

The Quadratic Sieve is identical to the GNFS, except for the very very last step, the "square root" step.

See Wikipedia's article on the Quadratic Sieve for a 1000-ft view of the algorithm.

To understand the "square root" step of the GNFS, you need to understand abstract algebra.

Note: I had to read several of these PDFs before I "got it", so don't get discouraged--its quite advanced. Again, to understand the full algo. you need to know abstract algebra. I'd recommend learning the Quadradic Sieve first.