The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
98 views

Efficient deterministic algorithms of factorizing

My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$. Are there such algorithms that use poly$(n, \log q)$ bit operations? I know ...
11
votes
1answer
427 views

An efficient isomorphism between finite fields

Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
3
votes
0answers
107 views

Structured factoring

Is it easier to factor $$(ax + b) (ay+ c)=M$$ where $a,b,c\in\Bbb N$ are known where $b$ and $c$ are similar in size and $a$ is approximately $b^{2/3}$ and unknowns $x,y\in\Bbb N$ and are ...
1
vote
0answers
70 views

Algorithm for checking linear independence of algebraic numbers

Is there any if and only if condition for checking $Q$-linear independence of given a set of numbers say $\alpha_i$ ? More precisely how to check linear independence of given $n$ algebraic numbers (...
5
votes
0answers
115 views

Primitive element for a number field, and ramification

Let $K=\mathbb Q(\theta)$ be a number field with integral primitive element $\theta$, and let $f(x)$ be the minimal polynomial of $\theta$. Let $p$ be a rational prime. It's well known that if $p$ ...
0
votes
0answers
105 views

More generalized RSA construction

Is there a way to construct RSA type cryptosystem over general number rings? Can Number Field Sieve technique be applied here?
2
votes
0answers
61 views

Algorithm to generate random polynomials which has root in Q(a) where a is another algebraic number

Suppose you are given an algebraic number $\alpha$ . It is represented by $(p(x),(a,b),r)$ where $p(x)$ is its minimal polynomial. $a+ ib$ is an approximation of $\alpha$ such that there is no other ...
4
votes
1answer
176 views

Computing coefficients for the slash operator of a modular form

Suppose $f$ is a classical modular form of weight $r$ for a (congruence) group $\Gamma$. Let $\gamma$ be any matrix in $\operatorname{SL}_2(\mathbb{Z})$. Then the slash operator $|_\gamma$ is usually ...
1
vote
0answers
93 views

parametrizing a conic in $F_p$ [closed]

Let $F_p$ be a finite field and $p\equiv 3 \pmod 4$, and $a,c$ are non-square elements in $F_p$. I want to parametrize the conic: $$cy^2=-3x^2-2ax-16a$$ ($-1$ and $3$ are non-squares in this field ...
1
vote
1answer
183 views

Complexity of $\mathsf{gcd}(a,b)\bmod N$

Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$. My query is given $N,a,b$ where $a,b$ is $n$-bits ...
7
votes
0answers
233 views

Proving Richardson's theorem for constants

(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...
4
votes
1answer
356 views

On the mixed sum of three k-th powers

Let the set $S_k=\{\pm x^k \pm y^k \pm z^k \ \vert \ x,y,z \in \mathbb{Z} \}$. Note that the signs are independently positive or negative. First of all $S_2 = \mathbb{Z}$ because (see the answers ...
5
votes
1answer
269 views

The limit of the following product? What is the closed form of the value?

Assume that $P_n$ is the $n$'th prime: Please help me solve the following $$\lim_{k\to\infty} {k}\prod_{n=1}^k \frac{P_{2n-1}}{P_{2n}}$$ I am not really sure quite where to start here as I am ...
10
votes
2answers
504 views

Why going to number fields in number field sieve help beat quadratic sieve?

To factor an $n$ bit integer number field sieve roughly takes $$e^{c{(\ln\ln n)^{\frac23}}({\ln n})^{\frac13}}$$ time while quadratic sieve takes $$e^{c{(\ln\ln n)^{\frac12}}({\ln n})^{\frac12}}$$ ...
10
votes
2answers
503 views

Computing millions of coefficients of non self-dual modular forms

To test some conjectures made by some colleagues, I need to compute millions of coefficients of non self-dual modular forms, preferably in low weight (say 2 or 3). A form such as this. For elliptic ...
3
votes
1answer
136 views

Equivalence between Diffie Hellman and Discrete Log

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent? Is there any group for which we suspect them to be different? Could there be a finite ...
2
votes
0answers
205 views

Avoiding Chinese Remainder Theorem

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
5
votes
0answers
128 views

On factorization algorithms for $\mathcal{O}[x]$

We know that $\mathsf{LLL}$ algorithm provides factorization procedure that runs in poly time for polynomials in $\Bbb Z[x]$ that are primitive. What other rings $\mathcal{O}$ can we use instead of $\...
2
votes
0answers
83 views

Computing the density of a set of multiples

Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
0
votes
0answers
48 views

Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
7
votes
2answers
520 views

On bounds for idoneal integer

What is the best known lower bound and upper bound known for such a number if it exists and have there been any attempts (computational including) to eliminate the existence of such a number in known ...
2
votes
1answer
311 views

A quadrant of residues

Assume that following inequality holds $$\mathsf{w,x,y,z<AB,AC,AD,BC,BD,CD<ABC,ABD,ACD,BCD<wx,wy,wz,xy,xz,yz}$$ with $$\mathsf{gcd(A,B)=gcd(A,C)=gcd(A,D)=gcd(B,C)=gcd(B,D)=gcd(C,D)=1}$$ ...
7
votes
1answer
239 views

Numerically double-checking formula with L-values

I'm working with a special case of Ichino's triple product formula, which for classical holomorphic newforms $f$, $g$ ,$h$ of weights $k$, $m-k$, $m$ (and central characters satisfying $\chi_f \chi_g =...
0
votes
1answer
232 views

A three variable linear diophantine promise problem

Given $a,b,c,s\in\Bbb N$ such that $(a,b,c)=1$ with promise that we have at most one triple $x,y,z\in\Bbb N$ such that $ax+by+cz=s$, what is a good algorithm that runs in $O(\log(abcs))$ time to find ...
2
votes
1answer
195 views

On Pell's equation

A post was made (Reduction from factoring to solving Pell equation) seeking clarification to solving $$x^2-Dy^2=1$$ to factoring when $D>0$. An answer was posted stating that to factor $N$, it ...
1
vote
1answer
82 views

Runge-Kutta convergence [closed]

I am facing a problem solving a ODE with a Runge-Kutta 4th order method: The expression in order to solve is : \begin{equation} Ay^{''}+By^{'}+Cy= Cu \end{equation} \begin{equation} y =OUTPUT \end{...
5
votes
1answer
315 views

Computing an eigencuspform in $S_2(\Gamma_0(1776))$

Consider $$\bar{\rho}:G_{\mathbb Q}\longrightarrow\operatorname{GL}_2(\mathbb F_7)$$ the residual 7-adic Galois representation attached to the elliptic curve $y^2=x^3+x^2-4x-4$ of conductor 48. Then $...
5
votes
0answers
316 views

Are there always at least *five* divisions?

@JosephO'Rourke asked a question about a Collatz like function related to primes: $f(n) = \begin{cases} n^2 & \text{if} \;n \;\text{is prime} \\ \lfloor n/2 \rfloor & \text{if} \;n \;\text{...
10
votes
4answers
572 views

Computing minimal polynomials using LLL

I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation $a$...
2
votes
0answers
122 views

algorithm to find a new point of small height in a number field extension

By the height of an algebraic number $\alpha$, I mean the absolute, logarithmic (additive) Weil height $h(\alpha)$; e.g. $h(2^{1/n}) = (\log 2)/n.$ If $K$ is a number field, let $\delta(K)$ denote ...
2
votes
0answers
105 views

Comparing the size of two sums

Let $q$ be a prime power and $\mathbb{F}_q$ be the field of $q$ elements. Let $\mathbb{F}_q[t]$ be the polynomial ring over $\mathbb{F}_q$. I am working on a research project, where I bounded a ...
1
vote
1answer
242 views

Error term for prime harmonic

What is known about the asymptotic behavior of $$ f(x)=\sum_{p\le x}\frac1p-\log\log x-B_1? $$ Of course by Mertens we know that $f(x)=o(1),$ but has more been proved (in terms of $O$ or $\Omega_\pm$,...
2
votes
1answer
274 views

Residues and values of Riemann Zeta function at some points

I need the following computational results for proving something. Let $1/2 + i\gamma_0$, be the first nontrivial zero of Riemann zeta function, $\zeta(s)$, i.e. $\gamma_0\sim 14.134...$. 1) what is ...
4
votes
0answers
179 views

Monte Carlo variant of Hilbert's Tenth Problem

Let $k \in \mathbb{N}$. Given an algorithm $\mathcal{A}$ which takes as argument a polynomial $P \in \mathbb{Z}[x_1,\dots,x_k]$ and either returns true or false, we say that $\mathcal{A}$ works for $P$...
7
votes
0answers
241 views

On the ratio of Gilbreath sequences

Definitions: let $n \in \mathbb{N}_{>0} \cup \{ \infty \}$ and let $E_n$ be the set of sequences $(d_i)_{i=1}^n$ such that $d_1=1$, $d_i$ is an even integer (for $i > 1$) and $0<d_i \le i$. ...
1
vote
1answer
165 views

What is the ring $A_{\Gamma}$ in the Cohen-Lenstra Heuristics?

I understand the work in Cohen and Lenstra's paper that leads up to the heuristics themselves, where they count weighted averages of functions defined over isomorphism classes of $A$-modules, where $A$...
2
votes
1answer
252 views

Computing all “suboptimal” rational approximations to $\pi/2$

I have an irrational number $\alpha$ ($\alpha=\frac\pi2$), and I would like to determine all integers $n\in[1,N]$ ($N=10^{16}$) that satisfy $$ n \epsilon(n)^2 \leq \tau $$ where $\tau$ is a known ...
3
votes
0answers
178 views

Fourier expansions of newforms at width-1 cusps

Let $f_E$ be the newform attached to the Elliptic Curve $E$ with cremona label $\textbf{100a1}$ and let $\alpha = \left[\begin{matrix} 1&0 \\ 10&1 \end{matrix}\right] \in SL_2(\mathbb{Z})$. ...
1
vote
0answers
228 views

Rings of algebraic integers as quotients of polynomial rings

The ring of integers $\mathcal{O}_K$ of a number field $K$ is always isomorphic to some ring of the form $\mathbb{Z}[x_1, ..., x_r]/\mathfrak{p}$, where $\mathfrak{p} \subset \mathbb{Z}[x_1, ..., x_r]$...
2
votes
3answers
262 views

How to define the input of computable function or Turing machine over real numbers

Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...
3
votes
0answers
149 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 \...
18
votes
0answers
1k views

Is formula valid for relating $\pi$ with ALL of its OEIS A002485(n)/A002486(n) convergents?

Could anyone try to prove that the below conjectured formula is valid for relating $\pi$ with ALL of its convergents - those, which are described in OEIS via A002485(n)/A002486(n)? $$(-1)^n\cdot(\pi -...
2
votes
1answer
111 views

Growth of the truncation of the integral multiples of an irrational number

Let $[a]$ denote the integral part of a real number $a$. Let $a$ be an irrational number and $b$ a real number greater than $1$. Consider the sequence $(b^n(na-[na]))$ with $n$ running on the ...
1
vote
2answers
340 views

Computational complexity of solution of Pell equation and more

What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity? And more,could ...
0
votes
1answer
107 views

Size of approximate solution of an integer relation

Let $X_1$, ..., $X_n$ be a list of real numbers. Consider an integer relation equation $A_1 X_1 + \ldots + A_n X_n = 0$ where $A_1$, ..., $A_n$ are unknown integers. Suppose somehow we are not so ...
3
votes
1answer
213 views

Calculating (n ^ fibonacci(k)) MOD m for a large value of k

The value of $k$ can be very large indeed (up to $10^{12}$). Is there an efficient way to calculate the output? Edit : 'm' is a prime number.
1
vote
1answer
280 views

Number Field Sieve for factorization with non-monic non-linear polynomial. Can't understand calculating ideal valuations

There is a paper "Factoring integers with the number field sieve" (download it here, for example). I can't understand how they reason the correctness of computing ideal valuations in the case of ...
2
votes
0answers
86 views

Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?

Background By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that $$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...
5
votes
2answers
451 views

Minkowski successive minima inequality for a lattice base?

Let $\Lambda$ be a lattice of $\mathbb{R}^n$, and $\lambda_i$ be the radius of the smallest ball containing $i$ linearly independent lattice vectors. The Minkowski successive minima inequality says ...
1
vote
1answer
309 views

Valid Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$ d=p_i-p_j\mod N,\quad i\ne j $$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 0, 1, 2, ...