Number theoretic algorithms | Logarithms

Pollard's rho algorithm for logarithms

Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem. The goal is to compute such that , where belongs to a cyclic group generated by . The algorithm computes integers , , , and such that . If the underlying group is cyclic of order , by substituting as and noting that two powers are equal if and only if the exponents are equivalent modulo the order of the base, in this case modulo , we get that is one of the solutions of the equation . Solutions to this equation are easily obtained using the extended Euclidean algorithm. To find the needed , , , and the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence , where the function is assumed to be random-looking and thus is likely to enter into a loop of approximate length after steps. One way to define such a function is to use the following rules: Divide into three of approximately equal size: , , and . If is in then double both and ; if then increment , if then increment . (Wikipedia).

Video thumbnail

David Harvey: Recent progress on deterministic integer factorisation

Abstract: There are several deterministic factoring algorithms of complexity N^(1/4+o(1)) going back to the 1970s. Last year Hittmeir lowered the exponent to 2/9, and I subsequently improved it further to 1/5. In this talk I will explain the key ideas behind these new algorithms. --------

From playlist Number Theory Down Under 9

Video thumbnail

Introduction to number theory lecture 17. Factorization.

This lecture is part of my Berkeley math 115 course "Introduction to number theory" For the other lectures in the course see https://www.youtube.com/playlist?list=PL8yHsr3EFj53L8sMbzIhhXSAOpuZ1Fov8 We discuss two methods for factorizing numbers discovered by Pollard: his rho method and hi

From playlist Introduction to number theory (Berkeley Math 115)

Video thumbnail

Solving a logarithm with a fraction

👉 Learn how to solve logarithmic equations. Logarithmic equations are equations with logarithms in them. To solve a logarithmic equation, we first isolate the logarithm part of the equation. After we have isolated the logarithm part of the equation, we then get rid of the logarithm. This i

From playlist Solve Logarithmic Equations

Video thumbnail

CTNT 2018 - "Elliptic curves over finite fields" (Lecture 4) by Erik Wallace

This is lecture 4 of a mini-course on "Elliptic curves over finite fields", taught by Erik Wallace, during CTNT 2018, the Connecticut Summer School in Number Theory. For more information about CTNT and other resources and notes, see https://ctnt-summer.math.uconn.edu/

From playlist CTNT 2018 - "Elliptic Curves over Finite Fields" by Erik Wallace

Video thumbnail

Combining Logs 2

This is an worked example of logarithms in Algebra 2.

From playlist Logs Group Quiz

Video thumbnail

DLP Attacks and intro to El Gamal

We cover basic attacks on the discrete logarithm problem. The El Gamal Cipher is presented. We start discussion digital signatures.

From playlist PubKey

Video thumbnail

Isolating a logarithm and using the power rule to solve

👉 Learn how to solve logarithmic equations. Logarithmic equations are equations with logarithms in them. To solve a logarithmic equation, we first isolate the logarithm part of the equation. After we have isolated the logarithm part of the equation, we then get rid of the logarithm. This i

From playlist Solve Logarithmic Equations

Video thumbnail

Simplifying Logarithms 3

In this video, we simplify a logarithm.

From playlist Logs - Worked Examples

Video thumbnail

Solving the Logarithmic Equation log(A) = log(B) - C*log(x) for A

Solving the Logarithmic Equation log(A) = log(B) - C*log(x) for A Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys

From playlist Logarithmic Equations

Video thumbnail

Show that if f(x) = log(x/(x - 1)), then f(y + 1) + f(y) = log((y + 1)/(y - 1))

In this video we are given f(x) = log(x/(x - 1)) and we have to show that f(y + 1) + f(y) = log((y + 1)/(y - 1)). We do this by using properties of logarithms. I hope this helps someone who is learning algebra and studying logarithms. Basic Mathematics Book: https://amzn.to/3GN97j3 This i

From playlist Logarithmic Functions

Video thumbnail

Andras Gilyen - Quantum Algorithms for Quantum Information Processing Tasks - IPAM at UCLA

Recorded 24 January 2022. Andras Gilyen of the Renyi Institute of Mathematics presents "Quantum Algorithms for Quantum Information Processing Tasks" at IPAM's Quantum Numerical Linear Algebra Workshop. Abstract: Quantum linear algebra methods, in particular block-encoding and quantum singu

From playlist Quantum Numerical Linear Algebra - Jan. 24 - 27, 2022

Video thumbnail

Introduction to number theory lecture 1.

This lecture is the first lecture of my Berkeley math 115 course "Introduction to number theory" For the other lectures in the course see https://www.youtube.com/playlist?list=PL8yHsr3EFj53L8sMbzIhhXSAOpuZ1Fov8 This lecture gives a survey of some of the topics covered later in the course,

From playlist Introduction to number theory (Berkeley Math 115)

Video thumbnail

Solving a simple logarithm

👉 Learn how to solve logarithmic equations. Logarithmic equations are equations with logarithms in them. To solve a logarithmic equation, we first isolate the logarithm part of the equation. After we have isolated the logarithm part of the equation, we then get rid of the logarithm. This i

From playlist Solve Logarithmic Equations

Video thumbnail

Lenstras Algorithm

For more cryptography, subscribe @JeffSuzukiPolymath

From playlist Elliptic Curves - Number Theory and Applications

Video thumbnail

Solving for a variable by converting to exponential

👉 Learn how to solve logarithmic equations. Logarithmic equations are equations with logarithms in them. To solve a logarithmic equation, we first isolate the logarithm part of the equation. After we have isolated the logarithm part of the equation, we then get rid of the logarithm. This i

From playlist Solve Logarithmic Equations

Video thumbnail

IMO Longlist is Wild.

Train your Algebra Expertise by trying out Brilliant! =D https://brilliant.org/FlammableMaths Check out my newest video over on @FlammysWood! =D https://youtu.be/vPVA5Nv4IxA Wuck. https://play.google.com/store/apps/details?id=org.flammablemaths.Wuck Support the channel by checking out Deez

From playlist Improvised Sessions

Video thumbnail

Solving an logarithmic equation

👉 Learn how to solve logarithmic equations. Logarithmic equations are equations with logarithms in them. To solve a logarithmic equation, we first isolate the logarithm part of the equation. After we have isolated the logarithm part of the equation, we then get rid of the logarithm. This i

From playlist Solve Logarithmic Equations

Video thumbnail

x^y = y^x

Logarithmic differentiation In this video, I calculate the dy/dx, where x^y = y^x, and I do this in the language Newton originally used to publish his Principia Mathematicae. Enjoy this travel back in time! :) Subscribe to my channel: https://www.youtube.com/c/drpeyam

From playlist Random fun

Related pages

Prime number | Extended Euclidean algorithm | Integer factorization | If and only if | Pohlig–Hellman algorithm | Function (mathematics) | Integer | Pollard's rho algorithm | Discrete logarithm | Divisor | Cyclic group | Group (mathematics)