RSA - "public" and "private" key

[vivid nexus]

cyclic group of order m

• means under multiplication, removing non units

only elements coprime to m are invertible

then a^phi(m) = 1 mod m is an immediate consequence of euler's theorem

[icy valve]

what

look

what I know is this

2 to the power of k mod 5

has a cycle

in this case 243124312431

etc

cycle length is 4

and the cycle length always has to be a factor of phi(m)

is that not right?

[vivid nexus]

I'm not sure what you mean by cycle

[icy valve]

the cycle 24312431243124312431

for 2^k mod 5

[vivid nexus]

what do you mean with "cycle"?

[icy valve]

2^1 mod 5 = 2

2^ 2 mod 5 is 4

2^3 mod 5 is 3

2^4 mod 5 is 1

[vivid nexus]

ah

[icy valve]

2^5 mod 5 is 2

[vivid nexus]

this is called a subgroup generated by one of the elements

[icy valve]

can this be used to prove?

[vivid nexus]

this is used to prove euler's theorem, yes

if you have a group G then any element raised to the order of G is the identity

[icy valve]

how so

[vivid nexus]

you basically look at the subgroup generated by the element then use lagrange

not sure how I would explain this without actual group theory

I'd recommend you just pick up a book like artin or whatever and give it a read

[icy valve]

one second

can we collect all the formulas

we've written so far

p=prime
a^p = a mod p
a^(p - 1) = 1 mod p

a coprime m
a^(phi(m)) = 1 (mod m)

is this true?

[vivid nexus]

no

a^(p - 1) = 1 mod p is only true when a and p are coprime

[icy valve]

well duh

p is a prime number

so only true when a =/= p

[vivid nexus]

take a = 2p

then gcd(a, p) = p

[icy valve]

why would a = 2p

[vivid nexus]

why wouldn't it

[icy valve]

because we havent done it

we are usually given decimal natural numbers

not a = 2p

[small laurel]

( @vivid nexus they are in school and their teacher decided to show them some uni math lol - so naturally they don't really know a lot about the terms and foundation)

[vivid nexus]

yes, but what if

we have to cover all cases

not just the ones we might use

[small laurel]

u earlier said that the gcd must be 1. but that doesn't necessarily have to be the case, if a was picked "badly" and is a multiple of p

[icy valve]

uh

[small laurel]

that was the point they tried to make

[icy valve]

a^(phi(m)) = 1 (mod m) works only if a and m are coprime does it not?

[icy valve]

i unfortunately didnt understand it

[vivid nexus]

yes

[icy valve]

ill just memorize that

[small laurel]

it would make sense if u would be able to do the proof urself now

but its too advanced i suppose

[vivid nexus]

I mean

idk the number theory proof

only the algebraic one

[icy valve]

if you think so

then I really dont want to try

lol

[small laurel]

it's all fair, but it's kinda hard to go into the rabbit hole without doing all the foundation first

[icy valve]

my exam is tomorrow

going too deep into the rabbit hole at this stage

might ruin it

[small laurel]

it's a bit surreal to talk with someone about advanced math who hasnt seen the sum sigma yet for example

the route ur teacher picked is a bit weird

[icy valve]

this whole subject is weird

its "extra math"

but the thing is

[small laurel]

on the good side, when u ever take some math course at uni, its not new to u anymore lol

[icy valve]

its designed so that people who do it dont have an advantage in normal math or in computer science

which is just very dumb

[icy valve]

i am already familiar with uni content

seeing as it is my third semester

ik this is weird

but I study university alongside school

actually, I think YOU helped me back in my first semester on a java assignment

[small laurel]

ah fair

[vivid nexus]

do you do computer science or mathematics

[icy valve]

so

we go back a long way

lol

[icy valve]

I do everything really

this semester i went math

but it was too complex

next semester ill tone it down a little

[vivid nexus]

what course are you taking

[icy valve]

linear algebra

its cursed

[vivid nexus]

some linear algebra courses introduce groups and rings and stuff

[icy valve]

I honestly rarely understand anything he says

and the fact that we must code assignments in LaTeX

[vivid nexus]

do you know set theory

[icy valve]

makes it way worse

because I am super unfamiliar and honestly just suck at writin LaTeX script

[vivid nexus]

😵‍💫

math is the most prereq heavy

if you don't have the prereqs you might as well not understand anything

[icy valve]

i know

which is why the only exam I ever submitted was economy

in which I got a pristine 1,0

aka full grade

[vivid nexus]

how do you submit an exam

[icy valve]

i have to submit all assignments

im a normal uni student so to speak

just obliged to go to school

[vivid nexus]

so am I

[icy valve]

and not obliged to submit any exams

but I have the same priviliges as other uni students

[vivid nexus]

you take exams, not submit them lol

[icy valve]

pff

I took mine online

so I kinda submitted it

but yes youre right

[vivid nexus]

what school year are you in

[icy valve]

tenth

[vivid nexus]

ah nice me too

[icy valve]

how old are you though

[vivid nexus]

15

[icy valve]

same

but not for long

turning 16 in 2 days

lol

@vivid nexus do you know your cryptology?

maybe RSA?

[vivid nexus]

I don't know cryptography

[icy valve]

aah

shame

but you know your algorithms well

props to you man

[vivid nexus]

algorithms?

[icy valve]

euler

number theory

[vivid nexus]

I know some math, yes

[icy valve]

you seem to know algebra

well

[vivid nexus]

yeah

[icy valve]

@vivid nexus

one small question

how do we get from a^p = a (mod p) to a^p-1 = 1 (mod p)

[vivid nexus]

a^p = a^(p - 1) * a

then you just divide out a on both sides

[icy valve]

a^p-1 * a is a?

wait

a^p-1 = a^p + a^-1 + a^1

a^-1 + a^1 = 0?

[vivid nexus]

what?

[vivid nexus]

where did I say that

[icy valve]

nvm that

a^p-1 * a= a^p + a^-1 + a^1
a^-1 + a^1 = 0?

this

[vivid nexus]

why is a^p-1 = a^p + a^-1 + a^1

[icy valve]

forgot the times a

[vivid nexus]

?

[icy valve]

a^p-1 * a

equals

a^p + a^-1 + a^1

[vivid nexus]

no

[icy valve]

why

[vivid nexus]

why would it

[icy valve]

what

a^p = a^(p - 1) * a

[vivid nexus]

you're asking "why is that false"

[icy valve]

how do you get to this

[vivid nexus]

I'm asking you "why should that be true"

[vivid nexus]

by definition of a^p?

this is like

very basic math

2^3 = 2^2 * 2

[icy valve]

what is p-1

[vivid nexus]

are you asking what subtraction is

[icy valve]

no