55 votes
Accepted

Why is integer factoring hard while determining whether an integer is prime easy?

What I think you're asking for are examples of search problems that seem to be hard, while a corresponding decision problem is solvable in polynomial time (but not totally trivial). It is true that ...
Timothy Chow's user avatar
33 votes
Accepted

Does any cubic polynomial become reducible through composition with some quadratic?

You should refer to Lemma 10 (page-233) in this paper by Schinzel where he proves that for any polynomial $F(x)$ of degree $d$ we have a polynomial $G(x)$ of degree $d-1$ such that their ...
Hhhhhhhhhhh's user avatar
  • 1,032
33 votes
Accepted

Non-trivial solutions for $-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac)$?

There is no such solution. Let $$ Q(a,b,c,d) = 2(ad-bc)(bd+ac) + (a^2-b^2)(c^2-d^2) $$ be the difference between the two sides of the equation, so we seek to solve $Q(a,b,c,d) = 0$. This is a ...
Noam D. Elkies's user avatar
27 votes

Why is integer factoring hard while determining whether an integer is prime easy?

In the particular case of primality testing, primality testing is easier than factoring mainly because $p$ is prime if and only if $\mathbb{Z}/p\mathbb{Z}$ forms a field. This has a lot of ...
JoshuaZ's user avatar
  • 6,090
23 votes

Primality of a number of more than 50k digits

Yes, it is possible, but it is close to the boundary of what is reasonable. See for instance this software that was recently used by Andreas Enge to prove the primality of $10^{50000}+65859$. It took ...
Aurel's user avatar
  • 4,878
21 votes

What computer program for automorphic forms

The only CAS's that have built-in support for modular and automorphic forms, as far as I know, are Sage and Magma. [Edit: I had forgotten Pari/GP, which will introduce substantial modular forms ...
David Loeffler's user avatar
21 votes
Accepted

Possible contemporary improvement to bounded gaps between primes?

I think that there is indeed some possibility to lower the bound, and this is something I've looked at seriously a few times. I spent a semester (in 2019) with the Computational Number Theory Group ...
Pace Nielsen's user avatar
21 votes

Why is integer factoring hard while determining whether an integer is prime easy?

Let me give a slightly different example. The Baumslag-Gersten group is a one-relator group with the presentation $\langle a, b \mid [a, a^b] = a\rangle$. This has a Dehn function which grows faster ...
Carl-Fredrik Nyberg Brodda's user avatar
20 votes
Accepted

Is there a way to specify a special kind of reciprocals of natural numbers?

This is a textbook example of a question for which one should turn to the OEIS for assistance. The first few elements of this set are $$ 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, ...
Terry Tao's user avatar
  • 108k
19 votes

Sum of squares and divisibility

This is not a complete answer, but just a way to transform the problem into one that can be attacked by brute force in some known way. Write $d_i^2=N/n_i$. Then your relation becomes $$\frac{1}{n_1}+ \...
Francesco Polizzi's user avatar
18 votes
Accepted

Can we compute the first $n$ digits of $\pi$ in $F(n)$ time?

Mahler proved(1) that for any $p,q$, $\left | \pi -\frac{p}{q} \right| > \frac{1}{q^{42}}$. It follows that if one can compute $2^{ 42n} \pi$ to within an error of at most $1$, one can compute the ...
Will Sawin's user avatar
  • 135k
17 votes
Accepted

Question on the 50th (known) Mersenne prime number

As Jan Grabowski notes, all the primes that you mention have been discovered by GIMPS. GIMPS draws a distinction between testing and double-checking. When a Lucas–Lehmer test is performed on a ...
Timothy Chow's user avatar
17 votes
Accepted

Using the Eichler-Selberg Trace formula to compute class numbers?

Generally speaking, formulas like the trace formula admit an uncertainty principle: To obtain an identity where one side is highly concentrated (e.g. a sum over a small number of class numbers, or ...
Will Sawin's user avatar
  • 135k
16 votes
Accepted

simple conjecture on palindromes in base 10

Using $$\frac{10^c-1}{9}=\sum_{m=0}^{c-1} 10^m,$$ the product in question equals $$\sum_{n=0}^{2a+2b+c-1}r(n)10^n,$$ where $r(n)$ is the number of times $n$ occurs among the numbers (counted with ...
GH from MO's user avatar
  • 97.8k
16 votes
Accepted

Representing field elements in a computer

You are looking at a computable field (if your focus is on the field), or a computable presentation of a field (if your focus is on the details of how elements and operations are coded). These objects ...
Arno's user avatar
  • 4,356
16 votes

Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$

Answer to Question 1. Yes, $E(\mathbb{Z})=F$. The inclusion $F\subseteq E(\mathbb{Z})$ follows from $E\subseteq E(\mathbb{Z})$ and Dickson's result $E=F$. It remains to show $E(\mathbb{Z})\subseteq F$...
Philipp Lampe's user avatar
16 votes
Accepted

Goldbach conjecture and other problems in additive combinatorics

It seems what you are asking is "If we have a precise asymptotic for the number of elements of a set, can we solve binary additive problems involving that set?" The answer in general seems ...
Mark Lewko's user avatar
  • 11.7k
16 votes
Accepted

Parity of number of solutions to Diophantine equations

While it’s unclear what you mean by “parity” when the number of solutions is infinite, all such questions have been answered by M. Davis, On the number of solutions of Diophantine equations, Proc. AMS ...
Emil Jeřábek's user avatar
16 votes

A little number theoretic game

(This is not an answer, but an extensive comment and numerical simulation about Grundy values.) I believe there is some level of confusion because there are actually two very similar games under ...
Gro-Tsen's user avatar
  • 29.8k
15 votes
Accepted

Expressing primes $p\equiv 1 \pmod 3$ in the form $p = x^2 + xy + y^2$

This is an elaboration of the answer that Noam Elkies provided in the comments. Suppose that $p=x^2 + xy + y^2$. Then note that $x$ and $y$ are small relative to $p$ (at most half as many digits). ...
15 votes

A little number theoretic game

Edit: I added code to compute the Nim values for the first $N$ positions of this game after the original post, as requested by @Timothy-Chow. Unfortunately my results don't match those given by @Peter-...
I. J. Kennedy's user avatar
15 votes
Accepted

Can every integer be written as a sum of squares of primes?

The answer is yes, and this follows from known results concerning the Waring-Goldbach problem.
GH from MO's user avatar
  • 97.8k
14 votes

Computation of a minimal polynomial

In Sage you can do something like: ...
Moritz Firsching's user avatar
14 votes

In which cyclic cubic number fields does there exist this type of unit?

The answer to question 1 is yes. Pick any field element $x_1$ outside the rationals. Let $x_2$ and $x_3$ be its conjugates under the Galois group. Then the cross ratio $$w=\frac{(x_1-1)(x_2-x_3)}{(...
GNiklasch's user avatar
  • 2,266
14 votes

Fermat's last theorem $\pm1$

[EDITED] It is likely that there are no solutions at all for $n \ge 4$. For $n \ge 5$ a solution would be a counterexample to the Lander, Parkin, and Selfridge conjecture. The best FLT "near ...
Robert Israel's user avatar
13 votes
Accepted

An efficient isomorphism between finite fields

Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (...
Michael Zieve's user avatar
13 votes
Accepted

Computational complexity of finding the smallest number with n factors

The problem asks for the least number $N$ such that the number of divisors of $N$ is at least $n+2$. Since all numbers below $N$ must have fewer divisors, clearly $d(N) > d(m)$ for all $1\le m <...
Lucia's user avatar
  • 43.3k
13 votes

Twin primes conjecture and extrapolation method

This is just to present a numerical curiosity. I suspect that it is coincidental, but I feel compelled to share it in case anyone wants to look further. First some disclaimers: Consider a random walk ...
Aaron Meyerowitz's user avatar
13 votes

Do consecutive integers have a big prime factor?

Shorey and Tijdeman, On the greatest prime factors of polynomials at integer points, Compositio Mathematica, tome 33, no 2 (1976), p. 187-195 http://www.numdam.org/item?id=CM_1976__33_2_187_0 note ...
Gerry Myerson's user avatar
13 votes
Accepted

Computational efficiency of character sums for counting finite field points on a curve

For numbers as small as $5$, it should make virtually no difference. Let me interpret this question as asking for a method to do it over any finite field. I will also restrict to the case of $\mathbb ...
Wojowu's user avatar
  • 27.3k

Only top scored, non community-wiki answers of a minimum length are eligible