# Tagged Questions

**7**

votes

**1**answer

502 views

### Can the Legendre symbol be calculated in polynomial time?

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...

**23**

votes

**1**answer

686 views

### How strong is this conjecture? $(Z/nZ)^*$ is generated by “small” elements

Conjecture: There are constants $c,k$ such that every $(Z/nZ)^*$ is generated by its elements smaller than $k (\log n)^c$.
Where $(Z/nZ)^*$ is the multiplicative group of integers mod $n$. My ...

**-6**

votes

**1**answer

138 views

### Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that $P-Q \neq 1$ and $N=P^2-Q^2$ [closed]

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that:
$P-Q \neq 1$ and $N=P^2-Q^2$
I am assuming that the best known solution to this problem runs at $O(2^{|N|})$.
...

**11**

votes

**1**answer

229 views

### Comparing two numbers given their factorization

I'm not an expert, but given the integer factorization of two numbers $a,b$:
$$a = p_{i_1}^{a_1}...p_{i_n}^{a_n}, \quad b = p_{j_1}^{b_1}...p_{j_m}^{b_m}$$
What is the time and space compexity of ...

**2**

votes

**1**answer

451 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...

**5**

votes

**1**answer

284 views

### Subsets of all Diophantine's sets

I have asked this question on math.stackexchange already:
http://math.stackexchange.com/questions/627461/subsets-of-all-diophantines-sets
Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable ...

**2**

votes

**0**answers

108 views

### Reference Request: Properties of the Integer Factorization Polytope

The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online ...

**2**

votes

**0**answers

217 views

### cyclotomic polynomials of given degree

Is there a fast algorithm to generate all cyclotomic polynomials $\Phi_n$ for which the degree of $\Phi_n$ is a fixed constant $d?$ This is obviously related to the "inverse totient" function: compute ...

**2**

votes

**0**answers

132 views

### Odds of projections of a point not on the hyperplane

Let $\mathcal{L}=\{\Bbb x\in\Bbb R^n:x_1+x_2+\dots+x_n=0\}$ be a specific hyperplane.
Let a projection of $c\in\Bbb R^n$ be $p(c)=[p_1,p_2,\dots,p_n]$ where $p_i\neq c_i\implies p_i=0$.
Let ...

**3**

votes

**2**answers

260 views

### Efficient representations of natural numbers via arithmetical expressions

A given natural number $n \in \mathbb{N}$ has many representations
as expressions mixing other natural numbers and the operators and punctuation symbols
$\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' ...

**6**

votes

**4**answers

483 views

### How long does it take to compute a class number?

I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the ...

**3**

votes

**2**answers

207 views

### Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$.
Given $g$ and either
$$ A = x g^ x$$
or
$$ A = x g^{x^2-1}$$
find $x$.
What is the complexity of solving this?
Is there a reduction to the discrete ...

**1**

vote

**1**answer

538 views

### The smallest altitude amongst the triangles formed by points in the unit circle

Let $S$ be a finite set of points inside the unit circle. Consider all possible triangles formed by three distinct points in $S$, and among all such triangles find the smallest altitude. Denote this ...

**13**

votes

**1**answer

417 views

### How fast can we numerically calculate Kloosterman sums?

Define the usual Kloosterman sum by $$S(m,n;c) = \sum_{\substack{x \pmod{c} \\ (x,c) = 1}} e\Big(\frac{mx + n\overline{x}}{c}\Big),$$
where $x \overline{x} \equiv 1 \pmod{c}$, and $e(x) = e^{2 \pi i ...

**2**

votes

**1**answer

294 views

### Problem to a solution

Consider an NP hard problem $\frak P$ which takes an input of length n
$\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...

**23**

votes

**1**answer

675 views

### Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether
...

**6**

votes

**2**answers

720 views

### Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...

**2**

votes

**0**answers

107 views

### supersingular curve detector

Suppose I give you a prime $p$ and ask for a non-CM supersingular elliptic curve over $\mathbb{F}_p.$ Can this be done in polynomial time (so, polynomial in $\log p$)?

**2**

votes

**3**answers

274 views

### Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties ...

**17**

votes

**1**answer

2k views

### Möbius Randomness of the Rudin-Shapiro Sequence

The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows.
Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...

**3**

votes

**3**answers

706 views

### Problem regarding subsets that sum to 0

Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset ...

**9**

votes

**1**answer

562 views

### Polynomial-time complexity and a question and a remark of Serre

My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a ...

**2**

votes

**2**answers

916 views

### Number theory and NP-complete

What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.

**7**

votes

**1**answer

613 views

### Finding colinear points in F_q^n

Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit.
Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let ...

**2**

votes

**0**answers

268 views

### Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...

**14**

votes

**3**answers

980 views

### symmetric integer matrices

Suppose I have a symmetric positive definite matrix $M$ with integer entries. I want to decide whether $M = A A^t,$ with $A$ likewise integral. I assume that decision problem is NP-complete, as is the ...

**8**

votes

**2**answers

405 views

### Efficient computation of the least fraction with square denominator greater than the square root of 2.

The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a ...

**11**

votes

**1**answer

340 views

### The complexity of the leading fractional bit of a power of a rational number

On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...

**1**

vote

**1**answer

360 views

### What are the consequences of a polynomial time algorithm for finding out if a given number is expressible as the sum of two squares?

This question is based on this question, in which it is asked if there is a polynomial time algorithm which finds out if a given number is expressible as the sum of two squares. One of the answers ...

**11**

votes

**1**answer

1k views

### Computing exponential sums rapidly?

I am looking at sums of the form
$\sum_{N\le n \leq N+M} e(P(n))$
where $P\in R[x]$ is a polynomial of bounded degree. Let's say $M\sim c N$ (and $N$ is large).
The question is - when can one ...

**32**

votes

**3**answers

3k views

### Testing whether an integer is the sum of two squares

Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer n is a sum of two squares?
By "fast" here I mean polynomial time (i.e. time O((log n)^{O(1)})). Note that ...

**37**

votes

**2**answers

5k views

### Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly Orthogonal to Morse
!
Harold Calvin Marston Morse (24 March ...

**21**

votes

**3**answers

2k views

### Discrete Fourier Transform of the Möbius Function

Consider the Möbius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Next consider for some natural number ...

**1**

vote

**1**answer

3k views

### Finding the square root modulo n, when the factors of n are known

Last month, I asked whether there is an efficient algorithm for finding the square root modulo a prime power here: Is there an efficient algorithm for finding a square root modulo a prime power?
Now, ...

**3**

votes

**3**answers

718 views

### A conjecture on a Subset Power Sum Problem motivated by Computer Science

Let $X=\{x_{1}, \cdots , x_{n}\}$ be a set of $n$ positive integers and integer $i \ge 1$. Let’s say that the set $X$ is $i$-sum-avoiding if for any nonnegative integers $c_{1}, \cdots, c_{n}$ such ...

**10**

votes

**3**answers

585 views

### Efficiently getting bits of N! ?

Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?
...

**11**

votes

**0**answers

565 views

### Regular languages of matrices and their generating functions

My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...

**6**

votes

**3**answers

1k views

### Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...

**5**

votes

**1**answer

262 views

### Speeding the quadratic sieve with an oracle

Suppose we have an odd composite $N$ and want to find numbers $a_1,\ldots,a_k$ such that each $a_i^2$, reduced mod $N$, is $b$-smooth. Of course we can use the quadratic sieve algorithm (minus the ...

**11**

votes

**2**answers

716 views

### Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...

**8**

votes

**3**answers

822 views

### Boolean Cube of Primes

For a large enough $n$, and a parameter $ m $ I'm looking for a subset of the prime numbers in the range $[n,2n]$ with a unique structure. I am looking for a prime $p$ and a set of $m$ positive (not ...

**12**

votes

**3**answers

2k views

### Zero-knowledge proof of positivity

If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?
My bounty is ending ...

**6**

votes

**2**answers

539 views

### Funky congruences

Suppose we have the remainders: {$(a^0_1, a^1_1), \ldots, (a^0_n, a^1_n)$} and the moduli {$c_1, \ldots, c_n$}. We want to know if there exists $b_1, \ldots, b_n \in$ {0,1} and $m \in \mathbb{N}$ such ...

**0**

votes

**2**answers

1k views

### Time complexity of finding the GCD of a set S as a function of sum(S)

The algorithm to be used is:
Sort the set into ascending order
$x_1 = s_1$
$x_i = gcd(x_{i-1},s_i)$
$GCD = x_n$
What I'm looking for is expected run time as a function of $\sum_{i\in S}i$
As a ...

**5**

votes

**4**answers

669 views

### Reconstructing a fraction from its first digits

It is not difficult to see that any reduced fraction $\frac{p}{q}$
where $0 < p < q $ and both $p$ and $q$ have at most $N$
digits (where $N$ is a fixed integer) can be reconstructed
from its ...

**12**

votes

**4**answers

986 views

### Complexity of testing integer square-freeness

How fast can an algorithm tell if an integer is square-free?
I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and ones conditional on GRH ...

**18**

votes

**4**answers

2k views

### Discrete logs vs. factoring

One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...