0
votes
0answers
21 views

Inverse modulo composite N

Let $N$ be composite and $a\in \Bbb N$ with $gcd(a,N)=1$. What is the best algorithm in terms of time complexity to calculate $x$ such that $ax\equiv 1\mod N$ when you are given $a \mod N$ and $N$?
1
vote
1answer
67 views

another counting problem

There are $k$ warriors that participate in the Wars, which have happened for the past $n$ years. Each year there has been a victor. Further, a particular warrior $W$ has won the Wars an even number of ...
1
vote
1answer
58 views

A problem on GCD

I want to calculate $f(n)$ where $f(n)$ is given by $$f(n) = \sum_{i=1}^n \dfrac{n}{gcd(n,i)}$$ and $2\leq n\leq 10^{12}$. Can someone tell me the fastest algorithm to calculate this. thanks
0
votes
0answers
26 views

Numerical calculation of an $x$ for which $\pi(x) > li(x)$

Littlewood 1914 proved that there are an infinite number of $x$ for which $\pi(x) > li(x)$. Skewes 1933 provided the first numerical upper bound on $x$ ...
-1
votes
1answer
67 views

Fermat Last theorem on Poly-Euler numbers

The poly-Euler numbers, denoted as $E_{n}^{(k)}$, are defined by the following generating functions :$${2\operatorname{Li}_k(1-e^{-x}) \over 1+e^{-x}}=\sum_{n=0}^\infty E_n^{(k)}{x^n\over n!}$$ The ...
0
votes
2answers
94 views

Existing Algorithm / Code to calculate exact values of the Riemann Zeta function at even natural numbers?

I wanted to know if there's any existing algorithm to compute exact values of the Riemann Zeta function at even natural numbers? For example, it should compute $\zeta(4)$ as exactly $\frac{\pi^4}{90}$ ...
3
votes
0answers
129 views

$\pi$, disjunctive numbers, and finite sequences of given length

It is an open problem whether the number $\pi$ is disjunctive in base $10$, i.e., whether every finite sequence appears (at least once) in the base $10$ expansion of $\pi$. Of course, every sequence ...
5
votes
1answer
1k views

A search for integers which can be written as a sum of two squares in multiple ways

As part of a number theory hobby project, I'm looking for a computational way to enumerate all integers $n$ which can be written as a sum of two integer squares in three or more ways. The range of ...
2
votes
1answer
96 views

Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval: $\{318, 921, 1526, ...
13
votes
1answer
1k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
4
votes
0answers
509 views

Obtain a contradiction

Motivation : The motivation is to show that the equation $x^{2b}.x^{2a} +(3-x^{2b}) x^{a} + (1-s^2)=0 $ has no solutions in integers for any values of $x,b,a,s$ ( choosen as per the constraints ...
17
votes
5answers
878 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
2
votes
1answer
96 views

Factoring short intervals

There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$. ...
9
votes
2answers
1k views

How to check whether an ideal is a prime (or maximal) ideal?

I have a ring $R$ which is known to be a Dedekind domain, but not necessarily a Euclidian domain, and a nonzero ideal generated by one or two elements in this ring. How can I check if this ideal is a ...
23
votes
1answer
467 views

Computing (on a computer) the first few (non-trivial) zeros of the zeta function of a number field

If $K$ is a number field, whose Galois closure over the rationals has degree 24 or so, and whose discriminant is around $163^4$, then what is a numerically efficient way of computing the first few ...
10
votes
2answers
886 views

How do I prove the partial denominators formula of the Bauer-Muir transformation of a generalized continued fraction?

Notation: $b_{0}+\underset{n=1}{\overset{\infty }{\mathbb{K}}}\left( a_{n}/b_{n}\right) $ is the Gauss Notation for generalized continued fractions. Description of the Bauer-Muir transformation ...