Loading ...
Sorry, an error occurred while loading the content.
 

Factoring n

Expand Messages
  • Jon Perry
    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),
      rad(n)?

      Which subsets do allow for a factorization of n?

      Jon Perry
      perry@...
      http://www.users.globalnet.co.uk/~perry/maths/
      http://www.users.globalnet.co.uk/~perry/DIVMenu/
      BrainBench MVP for HTML and JavaScript
      http://www.brainbench.com
    • andrew_j_walker
      ... 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),
        > rad(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
      • Jon Perry
        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/
          http://www.users.globalnet.co.uk/~perry/DIVMenu/
          BrainBench MVP for HTML and JavaScript
          http://www.brainbench.com
        • Paul Leyland
          ... 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
          • Jon Perry
            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/
              http://www.users.globalnet.co.uk/~perry/DIVMenu/
              BrainBench MVP for HTML and JavaScript
              http://www.brainbench.com
            • Paul Leyland
              ... 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?

                Nope. Please re-read what I said very much more carefully.


                Paul
              Your message has been successfully submitted and would be delivered to recipients shortly.