 mersenneforum.org Good Carmichael Number construction algorithm?
 Register FAQ Search Today's Posts Mark Forums Read 2018-03-04, 07:06 #1 carpetpool   "Sam" Nov 2016 5·67 Posts Good Carmichael Number construction algorithm? Suppose you are given a prime p and it is the largest prime factor of n, a Carmichael number with three distinct prime factors: n = p*q*r where gcd(p-1,q-1,r-1)=2?. Or in another case you are given two primes q and r of n and a prime p greater than q and r such that p*q*r is a Carmichael number (and of course gcd(p-1,q-1,r-1)=2). We already know that: q*r = 1 (mod p-1) r*p = 1 (mod q-1) and q*p = 1 (mod r-1) It is easy (and trivial) to solve any two solutions but solving the third remaining equivalence is a matter of complexity. For example, suppose we are given p = 4801 (the largest prime factor of n) and asked to find primes q and r such that n = p*q*r is a Carmichael number, gcd(p-1,r-1,q-1) = 2, and r < q < p. One would start by setting up the equivalences: q*r = 1 (mod 4800) q*4801 = 1 (mod r-1) r*4801 = 1 (mod q-1) But from here it seems that I am stuck. Any help? Thanks!   2018-03-04, 07:38 #2 CRGreathouse   Aug 2006 22·3·499 Posts Each of the phi(4800) = 1280 residue classes coprime to 4800 are (a priori) possible for q and r. But once you pick one that fixes the other. So you can search like this: Code: `findCar3(p)=forprime(r=3,p-6, if(gcd(r,p-1)>1, next); my(q=lift(Mod(1/r,p-1))); if(q>r && q

2, next); my(q=lift(Mod(1/r,p-1))); if(q>r && q 2018-03-04, 13:19 #3 JM Montolio A   Feb 2018 5·19 Posts Question. ¿Someone interested on try to solve the Carmichael conjecture? I find some rules on totient(n)=k. Can be we can make the last step. JM M.   2018-03-04, 13:51   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·52·132 Posts Quote:
 Originally Posted by JM Montolio A I find some rules on totient(n)=k. Can be we can make the last step. JM M.
totient(n) is multiplicative to distinct prime factors of n.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 5 2016-10-08 09:05 ixfd64 Hardware 11 2011-11-02 23:54 Erasmus Other Mathematical Topics 12 2010-04-13 23:33 flouran Math 2 2009-05-08 21:37 wpolly Math 0 2004-12-01 11:14

All times are UTC. The time now is 14:33.

Thu Jun 8 14:33:59 UTC 2023 up 294 days, 12:02, 0 users, load averages: 0.95, 1.11, 1.27