Finding an algorithm for factoring general numbers quickly (faster than known algorithms) seems difficult.
Easier (and more fun) might be finding algorithms to quickly factor certain classes of numbers of special form. These algorithms probably won't (initially) be useful for cryptanalysis, because these special classes will likely be small, so cryptographers can easily avoid their special forms.
A lot along these lines already exists: Special Number Field Sieve, algebraic factorization of Cunningham numbers and of Fibonacci numbers, and the fact that factors of Fermat numbers must have a special form. Many factorization algorithms, including trial division and the Elliptic Curve Method, could be interpreted as algorithms that work well if the input number is of the special form of having at most one large prime factor.
Inspiration: Surely there must be some tricks not yet discovered for factoring Fermat numbers. They are of extremely special form. But currently we are attacking them with only with ECM and trial division (though the latter limited to the special form of Fermat factors).
Ambitious next step: given a specific number, perhaps a number of high economic value, try to find a special form it belongs to and an algorithm for factoring that special form. Neither might have been discovered at the outset of the search.
AI might be useful. Train machine learning with a large collection of known special forms and known algorithms for factoring those special forms, then ask it to synthesize new algorithms for new special forms.
Also with AI: given a number, output special forms it belongs to that might have (possibly yet undiscovered) algorithms for fast factorization. For example, it should detect that a number is of the form b^n-1. The trained AI knows that some special forms are more likely than other special forms to have (possibly yet undiscovered) fast factorization algorithms. A human (or separate AI) can then try to find algorithms for the promising special forms.
No comments :
Post a Comment