## Factoring n

Expand Messages
• Given n and sigma(n) and phi(n), is it possible to deduce the factorization of n? How about if other functions are added to the list, e.g. mobius(n), tau(n),
Message 1 of 6 , Jul 8, 2003
Given n and sigma(n) and phi(n), is it possible to deduce the factorization
of n?

How about if other functions are added to the list, e.g. mobius(n), tau(n),

Which subsets do allow for a factorization of n?

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• ... factorization ... tau(n), ... Jon, http://www.math.niu.edu/~rusin/known-math/98/factor_phi gives a probablistic method using phi(n) about half way down.
Message 2 of 6 , Jul 9, 2003
--- In primenumbers@yahoogroups.com, "Jon Perry" <perry@g...> wrote:
> Given n and sigma(n) and phi(n), is it possible to deduce the
factorization
> of n?
>
> How about if other functions are added to the list, e.g. mobius(n),
tau(n),
>
> Which subsets do allow for a factorization of n?
>

Jon,

http://www.math.niu.edu/~rusin/known-math/98/factor_phi

gives a probablistic method using phi(n) about half way
down. Apparently each trial has ~50% chance of working,
but I've never actually tested it.

Andrew
• I know of the result that says if 30% of N-1 is factored, then it becomes more possible to factor N (excuse my lack of knowledge in this area - my research has
Message 3 of 6 , Jul 20, 2003
I know of the result that says if 30% of N-1 is factored, then it becomes
more possible to factor N (excuse my lack of knowledge in this area - my
research has not yet touched upon it fully).

Is there a similar result that allows N to be factored using knowledge of
other surrounding n's, e.g. N-k, .., N-1, N+1, ...N+j?

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• ... I think you may be confusing factorization of N with primality testing of N. I deduce this from the mention of 30% . If a number N is believed to be
Message 4 of 6 , Jul 22, 2003
Jon Perry wrote:

> I know of the result that says if 30% of N-1 is factored,
> then it becomes more possible to factor N (excuse my lack
> of knowledge in this area - my research has not yet touched
> upon it fully).

I think you may be confusing factorization of N with primality
testing of N. I deduce this from the mention of "30%".

If a number N is believed to be prime, and one has at least 30%
of the factorization of N-1, it is then straightforward to prove
whether N is prime.

With this sole exception (proving that the prime factorization
of N is just N) I know of nothing that makes factorization of
N any easier if one knows the partial factorization of N-1.
If it did, we would find Fermat numbers much easier to factor
than they actually are: we know the complete factorization of
N-1 in that case.

> Is there a similar result that allows N to be factored using
> knowledge of other surrounding n's, e.g. N-k, .., N-1, N+1,
> ...N+j?

Yes, subject to the proviso that N is prime and it is wished to
prove this. The factorization of N+1 can be used in a similar
manner, as can the factorization of quantities such as the
algebraic factors of N^6-1 (of which N-1 and N+1 are just two).
There are no known ways of exploiting the factorizations of
N \pm j to find the factors of N.

Paul
• If a number N is believed to be prime, and one has at least 30% of the factorization of N-1, it is then straightforward to prove whether N is prime. With this
Message 5 of 6 , Jul 22, 2003
'If a number N is believed to be prime, and one has at least 30%
of the factorization of N-1, it is then straightforward to prove
whether N is prime.

With this sole exception (proving that the prime factorization
of N is just N) I know of nothing that makes factorization of
N any easier if one knows the partial factorization of N-1.
If it did, we would find Fermat numbers much easier to factor
than they actually are: we know the complete factorization of
N-1 in that case.'

So are you saying there are no more Fermat Primes?

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• ... Nope. Please re-read what I said very much more carefully. Paul
Message 6 of 6 , Jul 22, 2003
Me:

> 'If a number N is believed to be prime, and one has at least 30%
> of the factorization of N-1, it is then straightforward to prove
> whether N is prime.
>
> With this sole exception (proving that the prime factorization
> of N is just N) I know of nothing that makes factorization of
> N any easier if one knows the partial factorization of N-1.
> If it did, we would find Fermat numbers much easier to factor
> than they actually are: we know the complete factorization of
> N-1 in that case.'

Jon:

> So are you saying there are no more Fermat Primes?