Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square












2












$begingroup$


Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)



Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.



Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.










share|cite|improve this question









New contributor




Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$

















    2












    $begingroup$


    Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)



    Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.



    Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.










    share|cite|improve this question









    New contributor




    Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      2












      2








      2


      1



      $begingroup$


      Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)



      Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.



      Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.










      share|cite|improve this question









      New contributor




      Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)



      Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.



      Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.







      algorithms






      share|cite|improve this question









      New contributor




      Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|cite|improve this question









      New contributor




      Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|cite|improve this question




      share|cite|improve this question








      edited 3 hours ago







      Nick Jewett













      New contributor




      Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 6 hours ago









      Nick JewettNick Jewett

      113




      113




      New contributor




      Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          2 Answers
          2






          active

          oldest

          votes


















          4












          $begingroup$

          In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
          Then we have $N + B^2 = A^2$.
          Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.



          What's left is to look at the pairs of divisors of $N$.
          If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
          So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.



          The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
          Looks like one is not easier or harder than the other.
          In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
          So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.



          Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
          (Link suggested by Apass.Jack)






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
            $endgroup$
            – Nick Jewett
            5 hours ago










          • $begingroup$
            I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
            $endgroup$
            – Nick Jewett
            5 hours ago



















          0












          $begingroup$

          This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.



          Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.



          This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.



          The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.






          share|cite|improve this answer









          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "419"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });






            Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104795%2falgorithm-given-a-large-semiprime-number-n-find-the-smallest-value-of-a-such%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            4












            $begingroup$

            In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
            Then we have $N + B^2 = A^2$.
            Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.



            What's left is to look at the pairs of divisors of $N$.
            If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
            So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.



            The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
            Looks like one is not easier or harder than the other.
            In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
            So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.



            Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
            (Link suggested by Apass.Jack)






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
              $endgroup$
              – Nick Jewett
              5 hours ago










            • $begingroup$
              I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
              $endgroup$
              – Nick Jewett
              5 hours ago
















            4












            $begingroup$

            In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
            Then we have $N + B^2 = A^2$.
            Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.



            What's left is to look at the pairs of divisors of $N$.
            If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
            So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.



            The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
            Looks like one is not easier or harder than the other.
            In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
            So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.



            Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
            (Link suggested by Apass.Jack)






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
              $endgroup$
              – Nick Jewett
              5 hours ago










            • $begingroup$
              I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
              $endgroup$
              – Nick Jewett
              5 hours ago














            4












            4








            4





            $begingroup$

            In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
            Then we have $N + B^2 = A^2$.
            Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.



            What's left is to look at the pairs of divisors of $N$.
            If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
            So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.



            The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
            Looks like one is not easier or harder than the other.
            In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
            So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.



            Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
            (Link suggested by Apass.Jack)






            share|cite|improve this answer











            $endgroup$



            In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
            Then we have $N + B^2 = A^2$.
            Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.



            What's left is to look at the pairs of divisors of $N$.
            If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
            So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.



            The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
            Looks like one is not easier or harder than the other.
            In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
            So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.



            Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
            (Link suggested by Apass.Jack)







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited 2 hours ago

























            answered 5 hours ago









            GassaGassa

            695310




            695310












            • $begingroup$
              Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
              $endgroup$
              – Nick Jewett
              5 hours ago










            • $begingroup$
              I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
              $endgroup$
              – Nick Jewett
              5 hours ago


















            • $begingroup$
              Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
              $endgroup$
              – Nick Jewett
              5 hours ago










            • $begingroup$
              I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
              $endgroup$
              – Nick Jewett
              5 hours ago
















            $begingroup$
            Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
            $endgroup$
            – Nick Jewett
            5 hours ago




            $begingroup$
            Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
            $endgroup$
            – Nick Jewett
            5 hours ago












            $begingroup$
            I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
            $endgroup$
            – Nick Jewett
            5 hours ago




            $begingroup$
            I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
            $endgroup$
            – Nick Jewett
            5 hours ago











            0












            $begingroup$

            This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.



            Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.



            This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.



            The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.






            share|cite|improve this answer









            $endgroup$


















              0












              $begingroup$

              This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.



              Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.



              This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.



              The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.






              share|cite|improve this answer









              $endgroup$
















                0












                0








                0





                $begingroup$

                This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.



                Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.



                This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.



                The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.






                share|cite|improve this answer









                $endgroup$



                This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.



                Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.



                This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.



                The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered 34 mins ago









                D.W.D.W.

                99.5k12121286




                99.5k12121286






















                    Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.










                    draft saved

                    draft discarded


















                    Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.













                    Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.












                    Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.
















                    Thanks for contributing an answer to Computer Science Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104795%2falgorithm-given-a-large-semiprime-number-n-find-the-smallest-value-of-a-such%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    GameSpot

                    日野市

                    Tu-95轟炸機