2

Aussuming I have given a really large number $n \in \mathbb{N}$ (let's say, $10^{80} \le n \le 10^{100}$) and I know all the divisors of every number $x=0,1,\ldots,n-1$.

Is there any simple, universal and not too time-consuming way to find out all divisors of $n$?

vauge
  • 323

1 Answers1

1

Apart from electronically, no.

Knowing the divisors of numbers less than $n$ isn't really going to help. You are still going to have to test divisors, which means that you might have to search for the first multiple of $p$ under the required number.

On the other hand, there are some relatively fast proggies that will factorise numbers in these ranges. 'factor for OS/2 and Windows etc'. They're quite good.

One, could consider finding the factors, say of 121, knowing the factors of 2 to 120. Even for simple tests, one has to search back to find the previous multiple of 7, or 11, or 13, etc.

On the other hand, if you are trying to factorise a mob of numbers that follow each other, such as 14400, 14401, 14402, 14403, 14404, 14405, 14406, ..., 14409, it is really useful to do things like pick out the multiples of 2, 3, 5, 7, etc, because if 7 divides 14406, it does not divide any of the others. But this sort of test supposes that you have access to all of the primes less than the square root.

wendy.krieger
  • 6,856
  • While knowing the factors of smaller numbers doesn't help one get the factors of $n$, it's true that knowing factors of $(n-1)$ allows you to determine (and also prove) primality of $n$ faster than without knowing them. The bad news is that if $n$ is not a prime, this approach will not give you the factors of $n$; just a proof that it is not a prime. – Peter Košinár Jul 18 '13 at 02:09
  • You really don't need to know the prime factors of $(n-1)$, since finding an example where $a^{n-1}\ne 1$ suffices to give a composite number. Knowing the factors of $(n-1)$ does help filter out Carmichael Numbers (like $60112011801$), which typically never has a period equal to a large prime as the period. – wendy.krieger Jul 18 '13 at 07:11
  • This is why I mentioned the "and also prove" part -- yes, "most" numbers can be easily shown to be composite by providing a witness showing that Fermat little theorem doesn't apply to them. This produces a proof of composite-ness, but doesn't provide a proof of primality if the number is a prime -- in order to verify it, one would need to go over all possible values of $a$ (until running into the smallest non-trivial factor of $n$). If one knows the factorization of $(n-1)$, it's possible to find a set of numbers which actually prove that $n$ is a prime (a "certificate of primality"). – Peter Košinár Jul 18 '13 at 08:59