Alternative method to solve quadratic Diophantine equations

For most types of quadratic Diophantine equations there exists an algorithm which makes it possible to find a solution (or solutions) over integers (good reference is here: https://www.alpertron.com.ar/METHODS.HTM).

However, those methods require at some stage finding integer divisors of some expression made of equation's coefficients (i.e. A,B,...F). When these are small, then this task is not an issue. However, for coefficients with many digits this becomes an arduous exercise.

Does anyone see a possibility of finding integer solutions of QDE without the need of factorization (i.e. finding integer divisors) along the process?

• Nothing good in this idea. I like more formalized approach. The basic idea is to bring some form to the binary equivalent. And instead, to solve large - can be reduced to some equivalent to the Pell equation. Such a problem always comes down to the Pell equation. Interest is finding the beautiful connection binary form with equation Pell. Here as you know don't want to lead the discussion. Here is the promotion of your site. Mar 30, 2016 at 14:35
• That is not my site individ. Could you please elaborate further on this? Mar 30, 2016 at 21:01
• There are several approaches and options. For example one of them can be. artofproblemsolving.com/community/c3046h1048219 You can do another record. The meaning is always the same, be reduced to a simpler equation Pell. Mar 31, 2016 at 4:27
• @individ -- see math.stackexchange.com/questions/1721471/… -- a separate entry to elaborate further on Pell's. Please use it if you have time and will. Mar 31, 2016 at 8:12

Probably there is no method easier than the method Dario Alpern presents.

Note that in general it is UNDECIDABLE, whether a given polynomial with integer coefficients has integer roots.

The case with $2$ variables and degree $2$ is completely solveable, but you already need some effort to do this.

You can write a program, for example, in PARI/GP. It can easily handle large numbers, and it can factor numbers upto about $60$ digits very fast. PARI/GP supports ECM and quadratic sieve methods. Of course, for $500-600$ digits, some luck is needed to get a factorization in a reasonable time. But checking whether a number is prime is routine even for $500-600$ digit numbers.

As fas as I know, you have to program the methods yourself, PARI/GP does not have a command solving quadratic equations.

• Thanks. I know it's solveable, but for coefficients of say, 500-600 digits you would need a mainframe to compute this in a reasonable timespan (even though the coefficient expression to factorize is not as hard as for instance RSA numbers, but still -- they may include longish primes, absurdly hard to find on a regular PC). Therefore the only option (apart from using a quantum computer and Shor's algorithm -- well, no thanks) is to find a new method based on pure math. Maybe we're still missing something from these QDEs, we do not see something. Mar 30, 2016 at 11:57
• If you use a program like PARI/GP, large numbers are no problem. And with some luck, it can factor even $500-600$ digit-numbers fast. But I am pretty sure, we need the factorization of some number in some cases. Mar 30, 2016 at 12:00
• Seriously? What kind of factoring algorithms does it implement? GNFS? ECM? Could you please elaborate more in a regular response please, so that I can upvote it? :) Mar 30, 2016 at 12:03
• I know :) That is why I am researching this. Mar 30, 2016 at 12:04
• OK, I will keep it secret :) Mar 30, 2016 at 12:09