adamwhitehat / gnfs Goto Github PK

Can you give more info about variables!
Thanks!

Hi,

Thanks for the time and effort to put this together. The resources linked to are great.

After testing the application, I found a few bugs/issues that I would like to point out. Since I have addressed them in my fork I would like to know if you would like me to open a PR to address any/or tall of them.

Details:

Testing with the following n:
316300508827
316406230007
3218147
4295229443
536870911

1. NullReferenceException: Serialization.Load.cs, Line 32:

Sometimes a leading , is appended to the Json resulting in the deserialized List<Relation> having a null relation. I did not spend time tracking down the source, but instead put a guard in to .TrimStart(',') the json read from disk to prevent the exception.

2. Exception thrown loading existing configuration data. Fixed with overload option in CreateGnfs.cs, Line 13 to allow user to create a new configuration overwriting one already on disk.

I added an optional default parameter bool createNewData = false to allow overwriting existing data for a given n. Sometimes the factorization fails and new parameters need to be set. This could be because of user parameters or other runtime issues in the code. In the case of the latter sometimes an exception is thrown trying to load the configuration from disk. In any case, the parameter allows creating new data, instead of loading the existing, and overwrites the existing configuration if exists.

To support the new optional overload:

• MainForm.cs
• Line 222: buttonCreate is enabled so the user can choose to load existing data or create new data.
• Line 333: Added parameter true when calling CreateGnfs when clicking btnCreate

3. IsRationalIrreducible exception throw in SquareFinder.cs, Line 88:**

This exception was thrown when !IsRationalIrreducible evaluated as true. I hit this exception twice and it crashes the form and decided to comment it out. Since IsRationalIrreducible is logged, I left the check in itself, but perhaps the entire block can be commented out. Additionally, even when the conditions hits the algorithm went on to factor the number. Not sure if that was supposed to happen. I also don't know the math so perhaps when IsRationalIrreducible == false maybe the poly can be used to directly factor n?

4. Unit Test Refactoring - I refactored unit tests to require running any given step has called the previous dependent steps and, that the step completed successfully. This was inspired by your existing check in step two. Otherwise, when you run a step, it could run forever waiting for the previous step to complete even if that step has not been executed.

5.Unit Test02 OutOfMemoryException

Although the windows form application is working, Unit Test02 is not completing on my system. It gets stuck after finding 38 relations and never finds any more even though it needs 70 to complete. The end result is, if you let it run long enough, an OutOfMemoryException is thrown. To be clear, it is not the GNFS code throwing the exception. Instead, it is because the logging in the test fills up the unit tests frameworks in memory buffer for the standard output from the test due to the repeated Console.WriteLine calls.

A fix for this would not be part of the PR. Instead, I think a better fix would to be to put a max iterations parameter in the core code. This, potentially default optional parameter, could then be used to either throw an exception, or return some result to indicate failure, to guard against the collect relations step running forever. For example, max iterations could limit total iterations allowed to run in total, or it could be used to specify how many iterations are allowed to execute with no relations being found. The later could be helpful in letting the user know if the supplied polynomial and other hyperparameters supply are inadequate to adequately collection relations, for example if they specified a too low of smoothness bound.

Thanks again. And let me know if you would like me to submit a PR to address any/all of these.

My fixes are here: https://github.com/alexhiggins732/GNFS-DotNet-POC/tree/feature/allow-overwriting-existing-configuration

Alexander Higgins.

Even running this program with the default settings loaded in i was unable to make this program run properly

Hey !

First of all great job on this project. I can tell you really did your research and put a lot of time and effort into this project. I want applaud you for that.

I was curious and wanted to ask you if the project is completely finished. If so, what is the biggest number you managed to factor using this algorithm and how long did it take ? I'm really fascinated with prime numbers and factors but I have nowhere near the knowledge to construct such a complicated algorithm. Good job !

Hi,

Can you show the minimum working code to factor RSA100 with this software?

Seth

Description
During the square root in GNFSCore/SquareRoot/SquareFinder.cs, it will find the positive and negative roots via inverse modulo. Then it compares it to the positive and negative (inverse) original polynomial which does not actually do anything nor make sense. Finally it does not make use of this anyway, and uses a cartesian product and searches all 2^d values.

According to the thesis An Introduction to the General Number Field Sieve by Matthew E. Briggs cited here, the norm function should be used to disambiguate this. It is computed as alpha^((p^d-1)/(p-1) where alpha should be both of the potential roots. However I also cannot figure out how to get this to work, as it is unclear what is a positive versus negative norm. The key is being consistent across the splitting field. But trial and error is an oversight that should be correctable. Unfortunately I cannot find the details to get this working.

I need just function Factorization(n) for get prime numbers. Is it possible?

Proposal/Summary
Use the extended euclidean gcd algorithm instead of a for loop.

Rationale
The for loop is inefficient when compared to using extended euclidean gcd algorithm to calculate multiplicative inverse.

Implementation
Details of the extended euclidean gcd are widely available and its use to calculate modular inverse is commonplace in arbitrary precision or big integer libraries.

Details/Concerns/Other things to consider
None.

After finding factor bases, when I click the "find relations" button the program crashes, I dont know if this is just me but here is my output log:
Output.log.txt

how to run this, i am clearly stupid and don't know how to make this program work, if someone could inform me that would be amazing