Tag Info

New answers tagged


It can be done using any method you have at your disposal. Obviously, the more efficient method you use, the more efficient your algorithm will be, but even using trial division will yield a significantly more efficient algorithm than if you used trial division for the entire factorisation. Algorithms based on elliptic curves are also commonly used since ...


Your assumption "(assuming finding remainder and division takes place in constant time)" is not fulfilled here. We are dealing with big numbers and division complexity is some function M(b) where M is the complexity of your multiplication algorithm, e.g., Schönhage-Strassen with O(b log b log log b). Schoolbook division is of order b². Note that for ...

Top 50 recent answers are included