3
votes
0answers
134 views

Algorithm to compute a common denominator of a finite set of rational numbers

Let $x_1,\dots,x_n \in \mathbb{Q} \cap (0,1)$ be fixed, but unknown, and assume that we know a number $K \in \mathbb{N}$ such that there is a number $N \in \{1,\dots,K\}$ such that $x_1 N,\dots,x_n N ...
6
votes
3answers
645 views

Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
8
votes
0answers
530 views

Recent Fast Multiplication Algorithms for Large Integers

The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al http://arxiv.org/abs/0801.1416 shows how to use $p$-adic numbers instead of $\mathbb C$ used in Furer's ...
9
votes
3answers
937 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. ...
5
votes
2answers
417 views

Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem. Inputs: A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...
0
votes
0answers
174 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 ...
1
vote
1answer
281 views

Computation for composition of polynomials

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...
7
votes
1answer
645 views

Best way to find a closest vector in a lattice

Let $v_1,\ldots,v_n$ be linearly independent vector in $\mathbb{R}^n$, and let $\Lambda=\oplus_i^n \mathbb{Z}v_i$. The question is, given a vector $w$ find the element $v$ of the lattice $\Lambda$ ...
13
votes
2answers
899 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 ...
5
votes
2answers
530 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 ...
5
votes
1answer
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 ...
0
votes
3answers
328 views

Differences of squares

Suppose I wanted to express a number $N$ as a difference of squares. For large $N$ this is in general difficult, as finding $N=a^2-b^2$ leads to the factorization $N=(a+b)(a-b)$. Even if the problem ...