"Prime Rewards" Credit Card

ewmayer · 2011-01-19, 22:30

I have a credit card with a 16-digit number, having the following properties:

1. The full 16-digit CC number is prime;
2. The rightmost 8-digit portion of the CC number is prime;
3. The rightmost 4-digit portion of the CC number is prime;
4. The CC number satisfies the standard checksum.

How many possible 16-digit numbers fit the criteria?

(Note: My actual credit card number fits this description, so there is a possible financial-fraud incentive in play here.)

Mini-Geek · 2011-01-19, 23:28

Without looking in to how the checksum affects it, and assuming log(5*10^[x-1]) is a good estimate for the chances of a x-digit number being prime, I estimate that 1 in 5458 credit card numbers satisfy the conditions. Given that there are about 10^15 combinations, (assuming all 1 million possible issuer IDs each have 1 billion accounts, and taking into account that the last digit is based on the previous 15...not likely now, but we're looking for any possible number, not just ones that are likely to occur today) I'd say roughly 183 billion possible numbers match your criteria. A great deal are eliminated, yes, but a great deal still remain, so your CC number is safe. I'm sure someone will come along with a more precise answer.

My estimates are rough, especially because I ignored the checkdigit, but I doubt it would have so much of an effect that it turns 183 billion into 1, or even 20000. I'd guess that it tends to be practically random
I wonder how much information regarding primality and/or factoring you'd have to give to usually be able to uniquely identify a CC number. e.g. would "the full 16 digits is prime, the last 15 digits has 2 prime factors, the last 14 digits has 2 prime factors, etc." be sufficient?

CRGreathouse · 2011-01-20, 00:02

Quote:

Originally Posted by Mini-Geek

I'd say roughly 183 billion possible numbers match your criteria.

I'd think more than that. If the 16-digit number is prime, then the last digit is relatively prime to 10*, so the odds improve by a factor of ~ (5/2)^2.

* 0000000000000002 and 0000000000000005 fail the Luhn test.

ixfd64 · 2011-01-20, 00:27

Man, I could see the headlines already...

"Mathematician becomes victim of fraud after posting credit card riddle online"

Batalov · 2011-01-20, 00:38

Ernst will be in trouble when his trash bins are raided (or mailbox snooped); the piece of evidence that will greatly narrow the search is the name of the issuing bank. This determines the leftmost four digits (or a small set of these).

If you ever asked yourself: 'why are all bomb recipes in movies are so bogus?' - that's because they know their liabilities. Here, anyone with material suggestions also sets h{im,er}self up for abetting the criminals.

CRGreathouse · 2011-01-20, 01:22

Improving the odds from one-in-a-trillion to one-in-a-billion...

Batalov · 2011-01-20, 02:00

Looks like much less than a billion if the first four digits are known; my shot is about (/10 is from parity test)
1766126 * 10^4/10 / l(10^15)
~= 51,134,585

CRGreathouse · 2011-01-20, 02:09

Quote:

Originally Posted by Batalov

Looks like much less than a billion if the first four digits are known; my shot is about (/10 is from parity test)
1766126 * 10^4/10 / l(10^15)
~= 51,134,585

I get ~2x that if you can get all 4 digits. I assumed you'd get 3 out of 4 which seems more likely to me.

Mini-Geek · 2011-01-20, 02:17

Quote:

Originally Posted by Batalov

the piece of evidence that will greatly narrow the search is the name of the issuing bank. This determines the leftmost four digits (or a small set of these).

According to the site linked earlier regarding the checkdigit, it's not just 4, but the first 6 digits that are the issuer identifiers. If you also are able to find the person's last 4 digits of a credit card number (much easier to find on receipts, etc. than the full number), you now know 10 of 16 of the digits of credit card number, including the checkdigit. That still leaves 6 digits, or 1 million possible numbers. But if this is the same card that you know contains the 16, 8, and 4 digit primes, and you have that many of the digits, you would probably be able to infer the remaining digits, or at least narrow it to just a handful.

R. Gerbicz · 2011-01-20, 02:20

Quote:

Originally Posted by Mini-Geek

Given that there are about 10^15 combinations,

Don't go to work in a bank! There are exactly 10^15 valid card combinations. (Fix all numbers, except the first, then there is only one possibility for the first digit to make it a valid card number that satisfy Luhn algorithm).

If we "forget" that the card is prime, but other 3 requirements are true, then it is easy to calculate this number:

Code:

s=0;forprime(p=2,10^8,s+=isprime(p%10000));return(s*10^7)
17673550000000

This suggests for the true problem s/log(10^16)*2*5/4=1.2*10^12 value.
By simple simulations running 10^6 random card numbers gives: 128, 112, 121, 148 valid card numbers, so it gives also about 120*10^10=1.2*10^12 approximation.

Mini-Geek · 2011-01-20, 03:12

Even when given the first 6 digits and last 4 digits (6 digits unknown) of an example credit card number I just tried, and given the 4 requirements in the first post, in the example I tried, 1,057 out of 1,000,000 numbers still remained. With the first 6 and last 5 (5 digits unknown), 119 out of 100,000 remained. These results approximately agree with R. Gerbicz's estimate: a little more than 1 out of 1,000 numbers remains after applying all those criteria. So to have a very good chance of calculating a credit card number based on the criteria, you can only be missing 3 of the digits. If you could try 6 wrong numbers (on average) without worrying, missing 4 of the digits would be ok, but that's still like having the financial institution and the last 6 of the card number, and they never reveal that much info.

2011-01-19, 22:30	#1
ewmayer ∂²ω=0 Sep 2002 República de California 103×113 Posts	"Prime Rewards" Credit Card I have a credit card with a 16-digit number, having the following properties: 1. The full 16-digit CC number is prime; 2. The rightmost 8-digit portion of the CC number is prime; 3. The rightmost 4-digit portion of the CC number is prime; 4. The CC number satisfies the standard checksum. How many possible 16-digit numbers fit the criteria? (Note: My actual credit card number fits this description, so there is a possible financial-fraud incentive in play here.) Last fiddled with by ewmayer on 2012-07-18 at 03:26 Reason: replace dead Luhn-link

2011-01-19, 23:28	#2
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts	Without looking in to how the checksum affects it, and assuming log(510^[x-1]) is a good estimate for the chances of a x-digit number being prime, I estimate that 1 in 5458 credit card numbers satisfy the conditions. Given that there are about 10^15 combinations, (assuming all 1 million possible issuer IDs each have 1 billion accounts, and taking into account that the last digit is based on the previous 15...not likely now, but we're looking for any possible number, not just ones that are likely to occur today) I'd say roughly 183 billion possible numbers match your criteria. A great deal are eliminated, yes, but a great deal still remain, so your CC number is safe. I'm sure someone will come along with a more precise answer. My estimates are rough, especially because I ignored the checkdigit, but I doubt it would have so much of an effect that it turns 183 billion into 1, or even 20000. I'd guess that it tends to be practically random I wonder how much information regarding primality and/or factoring you'd have to give to usually be able to uniquely identify a CC number. e.g. would "the full 16 digits is prime, the last 15 digits has 2 prime factors, the last 14 digits has 2 prime factors, etc." be sufficient? Last fiddled with by Mini-Geek on 2011-01-19 at 23:38*

2011-01-20, 00:27	#4
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 2·5·239 Posts	Man, I could see the headlines already... "Mathematician becomes victim of fraud after posting credit card riddle online" Last fiddled with by ixfd64 on 2011-01-20 at 00:28

2011-01-20, 01:22	#6
CRGreathouse Aug 2006 3×1,993 Posts	Improving the odds from one-in-a-trillion to one-in-a-billion... Last fiddled with by CRGreathouse on 2011-01-20 at 02:07

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
AMD Announces Industry's First "Supercomputing" Server Graphics Card	ET_	GPU Computing	23	2013-11-18 17:49
Speeding up double checking when first test returns "prime"	Unregistered	PrimeNet	16	2006-02-28 02:00
Oh noes! The "42nd Mersenne prime" isn't prime!	ixfd64	Lounge	7	2005-04-03 19:27
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2011-01-20, 00:38	#5
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	Ernst will be in trouble when his trash bins are raided (or mailbox snooped); the piece of evidence that will greatly narrow the search is the name of the issuing bank. This determines the leftmost four digits (or a small set of these). If you ever asked yourself: 'why are all bomb recipes in movies are so bogus?' - that's because they know their liabilities. Here, anyone with material suggestions also sets h{im,er}self up for abetting the criminals.

2011-01-20, 02:00	#7
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	Looks like much less than a billion if the first four digits are known; my shot is about (/10 is from parity test) 1766126 * 10^4/10 / l(10^15) ~= 51,134,585

2011-01-20, 03:12	#11
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 10253₈ Posts	Even when given the first 6 digits and last 4 digits (6 digits unknown) of an example credit card number I just tried, and given the 4 requirements in the first post, in the example I tried, 1,057 out of 1,000,000 numbers still remained. With the first 6 and last 5 (5 digits unknown), 119 out of 100,000 remained. These results approximately agree with R. Gerbicz's estimate: a little more than 1 out of 1,000 numbers remains after applying all those criteria. So to have a very good chance of calculating a credit card number based on the criteria, you can only be missing 3 of the digits. If you could try 6 wrong numbers (on average) without worrying, missing 4 of the digits would be ok, but that's still like having the financial institution and the last 6 of the card number, and they never reveal that much info.