# Tagged Questions

**2**

votes

**2**answers

158 views

### Integers up to n having an even number of trailing zeros in their factorial

It is well-known that the number of trailing zeros in the factorial $k!$ is given by the nice function $$ z(k) := \sum_{i \ge 1} \left\lfloor \frac{k}{5^i} \right\rfloor. $$
Now assume that we want ...

**0**

votes

**0**answers

69 views

### Minimize the length of two disjoint segments in the string with given property

You are given a string s of size n, consisting of characters A and B only. You have to find minimum sum of size of the two disjoint segments of the string s such that number of A's in them are >= z.
...

**3**

votes

**0**answers

125 views

### What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...

**0**

votes

**0**answers

63 views

### approximate coordinates in a one dimensional lattice

suppose I have a finite set of real numbers ${r_1, \ldots r_n \in \mathbf{R} }$ and a single real number $x \in \mathbf{R}$. Is there a fast algorithm for finding integer numbers ${i_1, \ldots i_n \in ...

**2**

votes

**1**answer

329 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 ...

**8**

votes

**1**answer

457 views

### How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...

**6**

votes

**4**answers

472 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 ...

**20**

votes

**4**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...

**3**

votes

**2**answers

202 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 ...

**2**

votes

**1**answer

253 views

### (efficient) method to test $\{n\alpha\}\not\in [A, B]\subset [0,1]$

Suppose $\alpha$ is a fixed given irrational number with $\alpha\in [A, B]\subset [0,1]$, are there any (efficient) methods to compute the least integer $n$ such that the decimal part of $n\alpha$ ...

**10**

votes

**7**answers

2k views

### Is there an algorithm to solve quadratic Diophantine equations?

I was asked two questions related to Diophantine equations.
Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all ...

**2**

votes

**1**answer

179 views

### RefReq: Algorithms for standard operations in Algebraic Number theory

Given an algebraic number field $F$ (I actually don't have an idea how to implement this data already, except for splitting fields of polynomials, but there is something in SAGE) is there free code ...

**27**

votes

**3**answers

1k views

### Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...

**1**

vote

**1**answer

126 views

### What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...

**3**

votes

**1**answer

205 views

### Is the prime ideal principal which is in 256-th cyclotomic ring lying over 257?

As we known, the integer ring R of 256-th cyclotomic field is not a Principal Ideal Domain.
And rational prime 257 is split completely in R.
Suppose prime ideal P of R is an arbitrary ideal lying ...

**3**

votes

**1**answer

330 views

### Fastest Digit Extraction for Any Irrational Number

I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for ...

**6**

votes

**2**answers

701 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

**1**answer

302 views

### At what point does Miller-Rabin become faster than trial division?

I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how ...

**9**

votes

**2**answers

584 views

### When polynomial f(x^2) can be factored as g(x)·g(-x) ?

In relation to my question Expression for the sum of square roots of zeros of a polynomial
How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where ...

**0**

votes

**0**answers

118 views

### Find polynomial in finite field

We have $A$, $B \in GF(q^k)$
We want to find polynomial $h \in GF(q)[x]$ where
$h(A) = B$
What is the lowest degree of $h$?
How to find $h$ with the lowest degree and what is complexity of this ...

**1**

vote

**1**answer

253 views

### Find root in finite field

What efficient algorithms exist for the solving $x^N = a$ in GF(q)?
What are their complexities?

**1**

vote

**1**answer

269 views

### calculate function from its divizor

There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$.
There is algebraic function f on C.
We have div(f).
How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + ...

**2**

votes

**0**answers

186 views

### Choosing a base where a given digit of a given number appears the most times

Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)

**1**

vote

**1**answer

244 views

### Computing the ratio of two large integers modulo m

$P(n)$ and $D(n)$ are two large integers.
Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer.
I want to compute $R(n)\bmod m$.
$P(n)$ and $D(n)$ are too large to be computed but $P(n)\bmod m$ and ...

**1**

vote

**5**answers

1k views

### The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ?
I tried going through this paper, but I couldn't understand the procedure.
Thanks

**2**

votes

**3**answers

1k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...

**2**

votes

**3**answers

269 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 ...

**1**

vote

**2**answers

710 views

### The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.
Preliminary: Mertens function and the ...

**9**

votes

**3**answers

836 views

### Mertens' function in time $O(\sqrt x)$

This MathOverflow question seems to indicate that the state of the art in computing
$$
M(x)=\sum_{n\le x}\mu(n)
$$
takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...

**3**

votes

**2**answers

615 views

### Find the maximum set whose subset sum is unique for every of its subset.

We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of numbers such that
for any $T_1,T_2\subseteq S$, the sum of ...

**6**

votes

**1**answer

596 views

### How this set of functions is ordered?

Notation:
$k, m, n$ are non-negative integers
$f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$
$f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$
$f \prec g$ means ...

**15**

votes

**5**answers

3k views

### Fastest Algorithm to Compute the Sum of Primes?

Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of ...

**5**

votes

**2**answers

297 views

### Feasibility of linear equations with few variables mod k

Say I want to verify the feasibility of
$$Ax \equiv b \text{ (mod } k)$$
where $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m}$ and $k \in \mathbb{N}$. Is there a fast way to verify if there ...

**2**

votes

**0**answers

288 views

### Algorithm for keeping a concrete version of Euclid's argument simple

(A version of this same question was posted to stackexchange.)
Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...

**3**

votes

**1**answer

387 views

### Find the least prime $p$ such that $mn$ divides $p-1$

My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.
Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ ...

**1**

vote

**0**answers

147 views

### Finding a set of congruences from a set of solutions

Let $S_1, \ldots, S_m \in \mathbb{Z}_2^n$ be $n$-tuples forming a subgroup of $\mathbb{Z}_2^n$. How can I find a set of congruences (mod 2) over $x_1, \ldots, x_n$ satisfying exactly $x_1 = S_j[1], ...

**0**

votes

**0**answers

172 views

### Number of biquadrates mod n

Is there an explicit formula for the number of fourth powers mod n?
Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for ...

**7**

votes

**2**answers

596 views

### Factoring some integer in the given interval

I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms.
Let N be a positive integer. Is there an efficient (i.e. ...

**8**

votes

**1**answer

637 views

### The Number of Short Vectors in a Lattice

Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the ...

**3**

votes

**0**answers

204 views

### Implementation for computing Shintani domains

By "Shintani domain", I mean a fundamental domain for the action of the totally positive units of a totally real number field k with $[k \colon \mathbb{Q}]=n$ (or more generally, those congruent to 1 ...

**11**

votes

**3**answers

739 views

### Bounds on squarefree numbers

Let $q_1,q_2,\ldots$ denote the squarefree integers 1, 2, 3, 5, .... What effective bounds are known for $q_n$? Clearly
$$q_n\sim\zeta(2)n$$
but I need hard inequalities. Of course from the above ...

**13**

votes

**2**answers

871 views

### Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...

**4**

votes

**1**answer

331 views

### Can we count primes in residue classes quickly?

Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in ...

**2**

votes

**5**answers

1k views

### partitioning a number into two sets based on sum of digits

hi, how can one determine whether a number belongs to such a set of numbers whose every element can be divided into two sets such that the sum of digits of each set of the number is same.
E.g
23450 ...

**6**

votes

**3**answers

805 views

### Prime counting - any fast alternatives to the Lagarias-Miller-Odlyzko combinatorial method or the Lagarias-Odlyzko analytical methods?

I guess the question says it all - I'm trying to track down fast algorithms for prime counting to know what's out there.
I'm already familiar with the two algorithms mentioned in the title ...

**7**

votes

**2**answers

472 views

### Algorithm for least distance of powers of integers

From Michailescu's theorem (Catalan's conjecture) we have that the only $a,b,m,n \in \mathcal{Z}^{+}$ with $m,n>1$ such that $a^{m} - b^{n} = 1$ are: $a=3$, $b=2$, $m=2$, $n=3$.
1) Is there an ...

**5**

votes

**2**answers

510 views

### Next (Restricted) B-Smooth Number Problem?

Given a bound, $B$, and a list of (small) primes $(p_0, p_1, \dots, p_{n-1})$ is there an efficient algorithm to find the next number greater than $B$ that can be expressed as a product of primes from ...

**10**

votes

**3**answers

584 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$?
...

**9**

votes

**4**answers

3k views

### Fast computation of multiplicative inverse modulo q

Given a large number $q$ (say, a prime) and a number $a$ between 2 and $q-1$ what is the fastest algorithm known for computing the inverse of $a$ in the group of residue classes modulo $q$?

**15**

votes

**4**answers

2k views

### FFTs over finite fields?

I'm trying to understand how to compute a fast Fourier transform over a finite field. This question arose in the analysis of some BCH codes.
Consider the finite field $F$ with $2^n$ elements. It is ...