Increase the number of digits in large integers

[worshipone]

Sorry to bother you, I would like to ask, if I want to decompose a 70-bit long integer, or longer, which parameters of the config should I modify?

[Richard-Van-Cyber]

Sorry to bother you, I would like to ask, if I want to decompose a 70-bit long integer, or longer, which parameters of the config should I modify?
Hello, sir, did you get the proper approaches to achieve this?

[NathanJepson]

@worshipone @greatfanfr

I will first qualify my answer by saying that I am by no means an expert in the General Number Field Sieve, and I don't have a mathematics degree.

I haven't ever gotten my project to factor a number as large as 70-bits, but I would be interested if you ever figured out a way to get it to do that.

Here are some ideas:

0. Some researchers were able to successfully factor a 512-bit number using GNFS, and I would review their paper for the tips and tricks that they used:
   https://link.springer.com/content/pdf/10.1007/3-540-45539-6_1.pdf
1. If you get somehow make a new mathematical discovery--a way to find polynomials which yield a high number of smooth pairs, more than the simple base-M expansion of the number "M"--that is currently an open area of research right now that you could pursue. The polynomial you select greatly effects the number of smooth pairs yielded, but GNFS researchers are still looking for ways to select the most effective polynomials when factoring large numbers.
2. You should definitely increase the size of the factor bases if you are factoring larger numbers. The size of the rational factor base and algebraic factor base are designated by "ub_rat_factor_base" and "ub_alg_factor_base" in the config file (you might need to also increase the size of the quadratic character base "ub_quad_character_base".) If you keep increasing the size of the factor bases with no luck, then try increasing the size of the sieve a bit at a time (the size of the sieve is governed by "a_lb","a_ub","b_lb","b_ub", as well as the "depth" variable.) However, increasing the size of the sieve increases the runtime by a whole lot though, so be prudent when increasing the size.

Mostly this project was just a way to help me understand a little bit of how the GNFS works, but I'm sure I implemented it incorrectly (someone with more background on the algorithm could improve it a lot.)

Good luck!

[Richard-Van-Cyber]

@worshipone @greatfanfr

I will first qualify my answer by saying that I am by no means an expert in the General Number Field Sieve, and I don't have a mathematics degree.

I haven't ever gotten my project to factor a number as large as 70-bits, but I would be interested if you ever figured out a way to get it to do that.

Here are some ideas:

0. Some researchers were able to successfully factor a 512-bit number using GNFS, and I would review their paper for the tips and tricks that they used:
   https://link.springer.com/content/pdf/10.1007/3-540-45539-6_1.pdf
1. If you get somehow make a new mathematical discovery--a way to find polynomials which yield a high number of smooth pairs, more than the simple base-M expansion of the number "M"--that is currently an open area of research right now that you could pursue. The polynomial you select greatly effects the number of smooth pairs yielded, but GNFS researchers are still looking for ways to select the most effective polynomials when factoring large numbers.
2. You should definitely increase the size of the factor bases if you are factoring larger numbers. The size of the rational factor base and algebraic factor base are designated by "ub_rat_factor_base" and "ub_alg_factor_base" in the config file (you might need to also increase the size of the quadratic character base "ub_quad_character_base".) If you keep increasing the size of the factor bases with no luck, then try increasing the size of the sieve a bit at a time (the size of the sieve is governed by "a_lb","a_ub","b_lb","b_ub", as well as the "depth" variable.) However, increasing the size of the sieve increases the runtime by a whole lot though, so be prudent when increasing the size.

Mostly this project was just a way to help me understand a little bit of how the GNFS works, but I'm sure I implemented it incorrectly (someone with more background on the algorithm could improve it a lot.)

Good luck!

Thank you very much for your sincere and warm answer, which is very helpful to me!