Skip to main content

Questions tagged [computational-number-theory]

This tag is for questions regarding to computational number theory, the branch of number theory concerned with finding and implementing efficient computer algorithms for solving various problems in number theory.

Filter by
Sorted by
Tagged with
0 votes
0 answers
63 views

gcrd and Associates of an element of the Quaternion algebra over a totally real number field $K$

Let $K$ be a totally real number field of class number 1, and $Q$ the quaternion algebra over the ring of integers of $K$ with basis $\{1,i,j,k\}$ such that $i^2 = j^2 = k^2 = -1$ and $ij = -ji, ik = ...
Don Freecs's user avatar
0 votes
0 answers
33 views

Real Life Applications of Two-Variable Quadratic Formulas

Where do two-variable quadratic formulas show up today as real-life combinatorial complexity challenges? Weather? Particle motion? Celestial calculations? Routing? Does anyone have specific examples? ...
Schmyndi's user avatar
1 vote
0 answers
40 views

Requesting for the Reference of multiplicative Property for Resultants [duplicate]

I have learned the definition of the Resultant of two polynomials Resultant of two polynomials. Following this definition, I want to see the proof of one property described in the "Characterizing ...
Afntu's user avatar
  • 2,215
1 vote
1 answer
75 views

Resultant $\mathrm{Res}_{x}(f(x), y - g(x))$ calculation and divisibility by $f$

I have learned the definition of the Resultant of two polynomials Resultant of two polynomials. In most places, it is defined over a field. Can we similarly define it for the general ring, for example,...
Afntu's user avatar
  • 2,215
17 votes
3 answers
1k views

One of the numbers $\zeta(5), \zeta(7), \zeta(9), \zeta(11)$ is irrational

I am reading an interesting paper One of the numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational by Zudilin. We fix odd numbers $q$ and $r$, $q\geq r+4$ and a tuple $\eta_0,\eta_1,...,\eta_q$ of positive ...
Max's user avatar
  • 910
3 votes
1 answer
47 views

Understanding what 'LLL-reduced in the direction of v' means

I've been working with ideal reduction algorithms, and in particular have a need to understand the notion of LLL-reduced along a vector $v$, and in particular what it actually means to have 'small $v$-...
Punchinello's user avatar
3 votes
0 answers
592 views

Factoring integers using trigonometric integrals

In this post, I want to ask the community about an issue regarding an analytical approach to dealing with the integer factorization problem. The problem definition is as follows: 1. Sets Let $C=\{x^2:...
Yapet G.'s user avatar
0 votes
0 answers
120 views

euler totient approximation

I want to find an approximation of Euler's totient. It`s for product n of two prime number a and b This is what I have actually: \begin{array}{} n = a.b\\ \varphi(n) = a.b - a - b + 1\\ \varphi(n) \...
PatternIsLife's user avatar
0 votes
1 answer
132 views

Prove correctness of algorithm that computes $\lfloor \sqrt{n}\rfloor$

I was looking in V. Shoup's book 'A Computational Introduction to Number Theory and Algebra' (freely available here). The exercise is as follows: As I'm not very familiar with proving correctness of ...
user avatar
0 votes
0 answers
19 views

Condition on the minimality of Minkowski units

I am interested in to undrestand when the Minkowski units in real biquadratic number fields are minimal in the log unit lattices. I have read some pieces of literature online which are investigating ...
Elei's user avatar
  • 79
2 votes
1 answer
117 views

Computing coefficients of $E_4^n$

This is a question about computing coefficients of modular forms, in particular about $E_4^4$, or $E_4^n$. Just a disclaimer, I am quite a beginner in this subject, and I am still slowly learning ...
Gareth Ma's user avatar
  • 3,772
0 votes
0 answers
66 views

Calculating modular roots over Gaussian integers

Let $a+bi$ be a Gaussian integer. Given another Gaussian integer $c+di$ how does one find $x^2\equiv(c+di)\bmod(a+bi)$? Can you illustrate with $x^2\equiv 48\bmod(156\pm89i)$?
Turbo's user avatar
  • 6,245
1 vote
0 answers
313 views

Finding Elliptic Curve based on Multiplicity and rational coordinates

We have to find an elliptic curve $E:= y^2=x^3+Ax+B $ (A, B are integers) which has points $P, Q$ with rational coordinates and satisfy $P=[n]Q, n>1$. So, Input: Rational coordinates = $P$. Output: ...
Consider Non-Trivial Cases's user avatar
1 vote
0 answers
67 views

Most efficient way to count primeomega(n)=4?

Problem: Given natural number N, count $\sum_{k\le N} [{\omega(k)=4}]$ This is the sequence of $\omega(k)=4$, we don't need to generate the sequence. Given a $N$, we need to know number of numbers in ...
sibillalazzerini's user avatar
4 votes
1 answer
182 views

Calculate $ \sum_{k=1}^{n} k\cdot \mu(k) $

Problem: Given $n$, Calculate $ \sum_{k=1}^{n} k\cdot \mu(k) $ This is the oeis series. My Thoughts: I need a sublinear algo, possibly something of the order of $n^{3/4}$ or $n^{2/3}$ time. Any ...
sibillalazzerini's user avatar
3 votes
2 answers
247 views

Calculate $ \sum_{k=1}^{n} k\cdot\varphi(k) $

Problem: Given $n$, Calculate $ \sum_{k=1}^{n} k\cdot \varphi(k) $ This is the oeis series. My Thoughts: Oeis gives a couple of approximate estimates/asymptotics but no real formula, exact closed form ...
sibillalazzerini's user avatar
1 vote
2 answers
96 views

Sum of co-primes of a number $n \le k$

Problem Given a number $n$ and a number $k$ ($k\leq n$) we are to find sum of co-primes of $n$ less than or equal to $k$ My thoughts factorise $n$ and then do $k(k + 1)/2$ - ...
sibillalazzerini's user avatar
3 votes
1 answer
227 views

Find efficient way to generate all solutions to Diophantine equation $a^2+5ab+3b^2-c^2=0$ under a given bound $N$

I am looking to solve Diophantine equation $a^2+5ab+3b^2-c^2=0$. a, b, c are all positive. Since the number of solutions are infinite. Lets say we are only interested in solutions till a limit N ie $1 ...
sibillalazzerini's user avatar
1 vote
0 answers
29 views

Reduced $O_K$-basis for a free $O_K$-module

Background: let $L \subset \mathbb{Q}^n$ be a lattice (i.e. a finitely generated $\mathbb{Z}$-module). Then $L$ has a reduced basis, that is, a $\mathbb{Z}$-basis $v_1, \dots, v_r$ satisfying $\prod_{...
vacant's user avatar
  • 638
2 votes
1 answer
42 views

Automating modular arithmetic in local fields using MAGMA

Let $f(X) = X^4 + a_3X^3 + a_2X^2 + a_1X + a_0$ be an Eisenstein polynomial over the $2$-adic numbers $\mathbb{Q}_2$. Let $\mathbb{Q}_2(\pi)/\mathbb{Q}_2$ be the totally ramified extension defined by $...
Sebastian Monnet's user avatar
1 vote
0 answers
35 views

For a given $N$ and a given prime $p_j$, count number of numbers that you can generate in ($N^{0.5}$, $N/p_j$] not divisible by any primes $ \ge p_j$

For a given $N$ and a given prime $p_j$ count the number of numbers can you generate in ($N^{0.5}$, $N/p_j$] that are not divisible by any primes $ \ge p_j$ Example: $N=100, p_j=5$ you can generate ...
ishandutta2007's user avatar
3 votes
0 answers
139 views

How to find order of a point on an elliptic curve?

Basic arithmetic of Elliptic curves: I want to see: The point $P=(1,1)$ is of order $4$ on the elliptic curve $y^2=x^3-x^2+x/\mathbb Q$. The following PARI/GP code gives answer: ...
MAS's user avatar
  • 10.8k
2 votes
0 answers
120 views

Efficient computation of $\prod_{p\equiv a\pmod m}(1-p^{-s})^{-1}$

Let $0<a<m$ be integers with $\gcd(a,m)=1$. For $s\in\mathbb{C}$ with $\Re s>1$, define $$\zeta(m,a;s)=\prod_{\substack{p\text{ is prime}\\p\equiv a\pmod m}}(1-p^{-s})^{-1}.$$ I'm looking for ...
metamorphy's user avatar
  • 40.1k
3 votes
0 answers
111 views

Identifying hyperelliptic curves as modular curves

I am reading Poonen's paper The Complete Classification of Rational Preperiodic Points of Quadratic Polynomials over Q: A Refined Conjecture. Several proofs require recognizing certain hyperelliptic ...
dummy's user avatar
  • 571
1 vote
1 answer
106 views

Query on $3^x \pm 2^{x-a}$ with relation to prime and semiprime

While doing some research(more closer to some playing) with the formula $3^x\pm2^{x-a}$ for $x\in \mathbb{N}$ and $ \{a\mid a \in \mathbb{Z}_{\geq 0},\hspace{1mm} a\le (x-1)\}$ I've become to observe ...
user1851281's user avatar
1 vote
1 answer
116 views

Does there exist a nontrivial prime power $q^k$ such that $\sigma(n^2)/n = q^k$ for some $n$?

Let $\sigma(x)=\sigma_1(x)$ be the classical sum of divisors of the positive integer $x$. My question in the present post is closely related to this one in MO: QUESTION Does there exist a nontrivial ...
Jose Arnaldo Bebita Dris's user avatar
1 vote
0 answers
125 views

Solving a Cyclic Polynomial by Radicals -- What Makes These Polynomials Different?

This is, at least spiritually, a follow-up to this question. But you don't need to have read it in order to understand this question. I'm working on implementing an algorithm to solve a cyclic ...
Chris Grossack's user avatar
8 votes
1 answer
277 views

Solving a Solvable Polynomial by Radicals (Effectively)

I'm trying to actually write some code (in sage) to take a polynomial $f$ with solvable galois group and compute its roots as nested radicals. Right now I'm just trying to get cyclic extensions to ...
Chris Grossack's user avatar
1 vote
1 answer
155 views

How to find Gaussian primes $10^6 < |\mathfrak{p}| < 2 \times 10^6$ with Pari-GP?

I am looking through the PARI/GP reference card. Example, listing primes over $\mathbb{Z}$ is standard computer homework exercise [1]: 100129 126691 193013 284933 492113 769591 How to write a ...
cactus314's user avatar
  • 24.5k
0 votes
1 answer
71 views

Show that the language wb^|w| (any string w over {a,b} followed by as many b’s as the size of w) is not regular.

Question : Show that the language wb^|w| (any string w over {a,b} followed by as many b’s as the size of w) is not regular. My proof (as per my opinion) is that: We suppose that w is a regular ...
ross's user avatar
  • 1
2 votes
0 answers
139 views

UFD with no efficient GCD algorithm

Is there a unique factorization domain where computing the GCD of two elements is thought to be computationally intractable? Here are some relevant results I've found: Wikström 2005 - For all rings ...
Marcel's user avatar
  • 343
4 votes
0 answers
174 views

Does these rational sequences always reach an integer?

Let $u_0 \ge 2$ be a rational, and $u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1)$. Question: Does the sequence $(u_n)$ reach an integer? It was checked by computer (with SageMath) for $u_0=\frac{p}{q}$ with $p \le ...
Sebastien Palcoux's user avatar
4 votes
0 answers
491 views

Efficient summation of multiplicative functions on intervals

Suppose that $f: \mathbb{N} \to \mathbb{C}$ is a multiplicative function; i.e., $f(mn) = f(m)f(n)$ if $m, n$ are coprime. I'm interested in efficiently calculating sums of the form $\sum_{k=1}^N f(k)$...
Thurmond's user avatar
  • 1,103
2 votes
0 answers
59 views

Division in higher dimensional ring of formal power series

Let $R$ be a ring with characteristic $0$. We can assume $R$ to be the $p$-adic field also, which is of course characteristic $0$. Let $f(x) \in R[[x]]$ be a power series and $f^{k}(x)$ be its $k$-th ...
MAS's user avatar
  • 10.8k
0 votes
0 answers
150 views

What are the mathematics journals focus on computational research article in number theory or algebra?

I know $\text{Mathematics of Computation(AMS)}$ is journal aiming research articles consisting of lots of computations. But this is one of the highest journals in this area to my knowledge. Is there ...
MAS's user avatar
  • 10.8k
3 votes
1 answer
324 views

Study and research in computational number theory

I am an undergraduate student and i have completed courses like data structures and algorithms , discrete mathematics , elementary number theory (i have studied Burton's book completely), abstract ...
TheReal__Mike's user avatar
3 votes
1 answer
347 views

How to find inverse of elements in a very large $\mathbb{Z}_n$ group?

Suppose I have an element $a\in\mathbb{Z}_n$ where $n$ is thousands of digits(base 10) and $\gcd(a,n)=1$. Is there a computationally efficient way of finding the inverse of $a$? or just any way to ...
ReverseFlowControl's user avatar
0 votes
0 answers
79 views

Compting the Legendre Symbol

Using the formula $$\left(\frac{a}{p}\right) \equiv a^{\frac{p - 1}{2}} \pmod{p}$$ for the Legendre symbol $\left(\frac{a}{p}\right),$ it takes only $O(\log p)$ steps to compute $\left(\frac{a}{p}\...
Venkataram Sivaram's user avatar
2 votes
1 answer
92 views

Variations of random coprime integers probability

The probability for two random integers to be coprime is $\frac{6}{\pi^2}$ (see for example this post), that is about $61\%$. After some computations, for $u_i, v_i$ random integers, the probability ...
Sebastien Palcoux's user avatar
4 votes
1 answer
218 views

Longest consecutive runs of sums of $k$-subsets of first $n$ primes

Table of contents [$1.$] Definition [$2.$] Implication. (Motivation.) [$3.$] Question. & Computed data. [$4.$] Solutions of simplified variations. [$5.$] Progress on solving the question. [$6.$] ...
Vepir's user avatar
  • 12.5k
3 votes
1 answer
160 views

Factoring Sieve Polynomial

I am dealing with a polynomial of the form $$p(a,b) = a^n - b^n $$ for integer values $a > b$, and some small integer $n$. I am wanting to factor this polynomial for a large range of values (for ...
mathymathymathymate's user avatar
3 votes
1 answer
121 views

generating function of sum of divisors function

It is well known that the function $$\sigma_k(n)=\sum_{d|n}d^k$$ has a generating function. For a number field $K$, suppose that $\mathfrak{a}, \mathfrak{b}$ are ideals in some ideal class $C$ and ...
R.T.'s user avatar
  • 41
1 vote
1 answer
52 views

how to split a separable algebra?

I'm trying to factor ideals in a function field (more precisely, ideals in a maximal order of a function field), and I've come across a step in the published Buchman-Lenstra algorithm which works in ...
Brent Baccala's user avatar
1 vote
1 answer
68 views

Probability the Fermat test returns "probably prime"

We aim to show that probability of odd $n>1$ passing the Fermat test for all bases a coprime to n is $$\frac{1}{\phi(n)}\prod_{p|n, p \ prime}gcd(p-1,n-1) $$where $\phi$ is the Euler totient ...
W M Seath's user avatar
  • 344
0 votes
0 answers
149 views

Testing whether two number fields are isomorphic

Could somebody point me to an implementation of an algorithm that takes two number fields $F$ and $L$, tests whether they are isomorphics, and if they are, returns an isomorphism? There is such a ...
fedlemming's user avatar
2 votes
0 answers
216 views

Is there an anomaly in the distribution of Mersenne primes?

In a recent press release off the Great Internet Mersenne Prime Search distributed computing project page, it is announced that $$2^{82589933} - 1$$ is the largest known (Mersenne) prime, ...
Jose Arnaldo Bebita Dris's user avatar