View Single Post
Old 2020-09-17, 22:30   #5
baih
 
baih's Avatar
 
Jun 2019

2·17 Posts
Default

greatest common factor
its clear that for a composite numbre n = ab

n-1 divide gcf(a-1,b-1)


if gcf are a big numbre we can use it for factoring n

this what make the contruction of RSA numbre (beware) of making gcf small and does not help for factoring

example

n= 14111 = 103* 137
14110 = 0 MOD 34


and of course gcf(102,136) = 34

Last fiddled with by baih on 2020-09-17 at 22:35
baih is offline   Reply With Quote